Комментарии 5
Известно, что метод BFS находит оптимальный путь от произвольной вершины в ориентированном графе до любой другой вершины, но это справедливо только для рёбер с единичным весом.
Свести задачу к решаемой BFS можно, но если заменить все рёбра неединичной длины n рёбрами длины 1
Можно и проще - в BFS вместо очереди использовать приоритетную очередь (т.е. упомянутую в статье кучу), будет "поиск по критерию стоимости", разновидность BFS
Это же и будет алгоритм Дейкстры. По крайней мере тот же вариант, который описан в статье в коде (в текстовом описании алгоритм в статье немного отличается от варианта в коде). Есть еще два варианта Дейкстры: 1 не помещать повторно в кучу то, что там уже находится, а просто выполнять heapifyUp для такого узла из кучи (минусы: куча с heapifyUp есть не в каждой библиотеке и ее придется реализовать самому; поддерживать указатели на узлы из кучи не так просто и ресурсозатратно; плюсы: используем О(n) памяти под кучу, а не О(m)), и 2 вообще изначально положить в кучу все узлы (минусы и плюсы в таком варианте те же)
Да, кажется что BFS с очередью с приоритетом, это и есть алгоритм Дейкстры. Только нужно не забыть, что минимизируется не длина следующего выбранного ребра, а сумма этого ребра и длины пути до текущей вершины
Почему в примере с отрицательными графами 5 не сравнивается с (10 - 6) = 4?
Потому что Алгоритм не переопределяет кратчайшие пути. Вершина C добавилась в граф первым шагом, и был определен кратчайший путь AC. Путь ABC короче, но если вершина C уже посещена, то этот факт игнорируеется.
В этом и суть неправильной работы с графами отрицательного веса. С ними работают методы динамического программирования
Алгоритм Дейкстры. Разбор Задач