Graph Algorithms Reference

Algorithm Type Neg edges Time Approach
Dijkstra Single source No O((V+E) log V) Greedy + heap
Bellman-Ford Single source Yes O(VE) DP relaxation
SPFA Single source Yes O(kE) avg BF + queue
Floyd-Warshall All pairs Yes O(V³) DP
Prim MST O((V+E) log V) Greedy + heap
Kruskal MST O(E log E) Greedy + Union-Find

阅读更多