主要最短路径与MST图算法之间的差异

Question

找不到该问题的综合答案。因此，将其放在此处并自己回答。

Answer 1

最短路径

1。 Dijkstra的算法

Single Source Shortest Path
Greedy Algorithm
Works for directed and undirected graphs
Does not work for negative edges and cannot detect negative cycles
Time Complexity O(E*log(V))

2。 Bellman-Ford算法

Single Source Shortest Path
Dynamic Programming
Works for directed and undirected graphs
Works on negative edges and detects negative edge cycles
Time Complexity O(V*E)

3。 Floyd-Warshall算法

All Source Shortest Path
Dynamic Programming
Works for directed and undirected graphs
Works on negative edges but cannot detect negative cycles
Time Complexity O(V3)

最小生成树

1。普里姆算法

Greedy Algorithm
Starts from any vertex
Does not work for directed graphs
Does not work on disconnected graphs
An edge may be considered multiple times
Better for dense graphs
Time Complexity O(E*log(V)) with Binary heap and O(E + V*log(V)) with Fibonacci heap

2。 Kruskal的算法

Greedy Algorithm
Starts from smallest edge
Does not work for directed graphs
Works on disconnected graphs
An edge is considered only once
Better for sparse graphs
Time Complexity O (E*log(v))