Я разработал взвешенный график, используя нормализованный список смежности в mysql. Теперь мне нужно найти кратчайший путь между двумя заданными узлами.
Я попытался использовать Dijkstra в php, но я не смог его реализовать (слишком сложно для меня). Другая проблема, которую я чувствовал, заключалась в том, что если я использую Dijkstra, мне нужно будет рассмотреть все узлы, которые могут быть, пожалуй, очень неэффективными на большом графике. У кого-нибудь есть код, связанный с вышеупомянутой проблемой? Было бы здорово, если бы кто-нибудь, по крайней мере, показал мне способ решения этой проблемы. Я застрял здесь почти неделю. Пожалуйста помоги.
Это звучит как классический случай алгоритма A *, но если вы не можете реализовать Dijkstra, я не вижу, чтобы вы вставляли A *.
A * в Википедии
edit: это предполагает, что у вас есть хороший способ оценить (но крайне важно, чтобы вы не переоценивали) стоимость перехода от одного узла к цели.
edit2: у вас возникают проблемы с представлением списка смежности. Мне приходит в голову, что если вы создаете объект для каждой вершины на карте, вы можете напрямую связать эти объекты, когда есть ссылка. Итак, у вас есть по существу список объектов, каждый из которых содержит список указателей (или ссылок, если хотите) к узлам, к которым они примыкают. Теперь, если вы хотите получить доступ к пути для нового узла, вы просто следуете ссылкам. Обязательно сохраните список путей, которым вы следовали для данной вершины, чтобы избежать бесконечных циклов.
Что касается запросов к БД каждый раз, когда вам нужно что-то получить, вам все равно придется это делать. Ваша лучшая надежда состоит в том, чтобы запрашивать только БД, когда вам НЕТ … это означает только запрос, когда вы хотите получить информацию о конкретном крае в графе или для всех ребер для одного вертекса на графике (последний, скорее всего, быть лучшим маршрутом), поэтому вы время от времени выбираете медленный ввод-вывод, а не гигантские куски сразу.
Вот грамотная версия алгоритма Дейкстры, на Java, которая может помочь вам разобраться, как реализовать ее в PHP.
http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29
Алгоритм Дейкстры возвращает кратчайшие пути от заданной вершины к другим вершинам.
Вы можете найти его псевдокод в Wiki .
Но я думаю, вам нужен алгоритм Флойда , который находит кратчайшие пути между всеми вершинами в DIRECTED grapth.
Математическая сложность обоих довольно близка.
Я мог бы найти реализацию PHP из Wiki для них обоих.