Согласно этой странице , алгоритм Дейкстры - это просто BFS с очередью приоритетов. Неужели это так просто? Думаю, нет.
algorithms
graphs
shortest-path
Барри Фрутман
источник
источник
Ответы:
Вы можете реализовать алгоритм Дейкстры как BFS с очередью приоритетов (хотя это не единственная реализация).
Алгоритм Дейкстры опирается на свойство того, что кратчайший путь от до также является кратчайшим путем к любой из вершин вдоль пути. Это именно то, что делает BFS.тs T
Или с другой точки зрения: как поведет себя алгоритм Дейкстры, если все веса будут равны 1? Точно так же, как BFS.
источник
Вот идея из книги «Алгоритмы (раздел 4.4)» Дасгупты и др.:
Для любого ребра из (с весом ) замените его ребрами длины , добавив фиктивные узлы между и .Е л е л е 1 л е - 1 U vе = ( и , v ) Е Lе Lе 1 le−1 u v
В результате все ребра графа результатов имеют единичную длину. Поэтому мы можем вычислить расстояния в , запустив BFS на . G G ′G′ G G′
BFS на может быть очень медленным, если некоторые велики, потому что они слишком много времени на вычисление расстояний до тех фиктивных узлов, которые нам совершенно не . Алгоритм Дейкстры избегает этого, устанавливая приблизительные расстояния для узлов и ослабляя их, когда это возможно.l eG′ le
Он ведет себя точно так же, как BFS. Мы разрабатываем это из двух основных моментов.
На "отдыхе".
Для алгоритма Дейкстры на общем взвешенном графе релаксация
Для BFS на невзвешенном графе мы знаем, что и , поэтому релаксация проще:w ( u , v ) = 1dist(v)=∞ w(u,v)=1
На «приоритетной очереди».
Когда алгоритм Дейкстры запускается на невзвешенном графике, в любой момент очередь с приоритетами содержит не более двух различных (дистанционных) значений. Следовательно, FIFO-очередь BFS достаточна.
источник