Прав ли я относительно различий между алгоритмами Флойд-Варшалла, Дейкстры и Беллмана-Форда?
Я изучал эти три, и я излагаю свои выводы из них ниже. Может ли кто-нибудь сказать мне, достаточно ли я их понял, или нет? Спасибо.
Алгоритм Дейкстры используется только тогда, когда у вас есть один источник, и вы хотите знать наименьший путь от одного узла к другому, но в таких случаях он терпит неудачу
Алгоритм Флойда-Варшалла используется, когда любой из всех узлов может быть источником, поэтому вы хотите, чтобы кратчайшее расстояние достигло любого конечного узла из любого исходного узла. Это терпит неудачу только при наличии отрицательных циклов
(это самый важный. Я имею в виду, в этом я меньше всего уверен:)
3. Беллман-Форд используется как Дейкстра, когда есть только один источник. Это может обрабатывать отрицательные веса, и его работа такая же, как у Флойд-Варшалла, за исключением одного источника, верно?
Если вам нужно посмотреть, соответствующие алгоритмы (любезно предоставленные Wikipedia):
Беллмана-Форда:
procedure BellmanFord(list vertices, list edges, vertex source)
// This implementation takes in a graph, represented as lists of vertices
// and edges, and modifies the vertices so that their distance and
// predecessor attributes store the shortest paths.
// Step 1: initialize graph
for each vertex v in vertices:
if v is source then v.distance := 0
else v.distance := infinity
v.predecessor := null
// Step 2: relax edges repeatedly
for i from 1 to size(vertices)-1:
for each edge uv in edges: // uv is the edge from u to v
u := uv.source
v := uv.destination
if u.distance + uv.weight < v.distance:
v.distance := u.distance + uv.weight
v.predecessor := u
// Step 3: check for negative-weight cycles
for each edge uv in edges:
u := uv.source
v := uv.destination
if u.distance + uv.weight < v.distance:
error "Graph contains a negative-weight cycle"
Дейкстр:
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity ; // Unknown distance function from
4 // source to v
5 previous[v] := undefined ; // Previous node in optimal path
6 // from source
7
8 dist[source] := 0 ; // Distance from source to source
9 Q := the set of all nodes in Graph ; // All nodes in the graph are
10 // unoptimized - thus are in Q
11 while Q is not empty: // The main loop
12 u := vertex in Q with smallest distance in dist[] ; // Start node in first case
13 if dist[u] = infinity:
14 break ; // all remaining vertices are
15 // inaccessible from source
16
17 remove u from Q ;
18 for each neighbor v of u: // where v has not yet been
19 removed from Q.
20 alt := dist[u] + dist_between(u, v) ;
21 if alt < dist[v]: // Relax (u,v,a)
22 dist[v] := alt ;
23 previous[v] := u ;
24 decrease-key v in Q; // Reorder v in the Queue
25 return dist;
Флойд-Воршалл:
1 /* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j
2 (infinity if there is none).
3 Also assume that n is the number of vertices and edgeCost(i,i) = 0
4 */
5
6 int path[][];
7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
8 from i to j using intermediate vertices (1..k−1). Each path[i][j] is initialized to
9 edgeCost(i,j).
10 */
11
12 procedure FloydWarshall ()
13 for k := 1 to n
14 for i := 1 to n
15 for j := 1 to n
16 path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );
2 ответа
Вы правы относительно первых двух вопросов и относительно цели Флойд-Варшалла (поиск кратчайших путей между всеми парами), но не относительно отношений между Беллманом-Фордом и Флойд-Варшаллом: оба алгоритма используют динамическое программирование для поиска кратчайшего путь, но FW - это не то же самое, что запуск BF от каждого начального узла до каждого другого узла.
В BF вопрос заключается в следующем: каков кратчайший путь от источника к цели с использованием не более k шагов, а время выполнения O (E V). Если бы мы запускали его на каждом другом узле, время выполнения было бы O (E V ^ 2).
В FW возникает вопрос: что является кратчайшим путем от i до j через k для всех узлов i,j,k. Это приводит к O(V^3) времени выполнения - лучше, чем BF для каждого начального узла (с коэффициентом до |V| для плотных графов).
Еще одно замечание об отрицательных циклах / весах: Дейкстра может просто не дать правильных результатов. BF и FW не подведут - они правильно заявят, что пути минимального веса нет, поскольку отрицательный вес не ограничен.
Кратчайшие пути из одного источника:
Алгоритм Дейкстры - отрицательный вес не допускается - O(E+Vlg(V))
Алгоритм Беллмана Форда - допускается отрицательный вес. Но если присутствует отрицательный цикл, Bellman ford обнаружит цикл -ve - O(VE)
Направленный ациклический граф - как следует из названия, он работает только для DAG - O(V+E)
Все пары кратчайших путей:
Алгоритм Дейкстры - отрицательный вес не допускается - O(VE + V^2lg(V))
Алгоритм Беллмана Форда - O(V^2E)
Метод умножения матричных цепочек - сложность, аналогичная алгоритму Беллмана Форда
Алгоритм Флойда Варшалла - использует метод динамического программирования - Сложность O(V^3)