[알고리즘] 최단 경로 알고리즘 비교 (Shortest Path Algorithms)

Shortest Path Algorithms

Algorithm	Complexity	Handle Negative weight?	Properties
Dijkstra	O((n+m) log n) O(n^2)	No	- Good for dense graph - Adjacency matrix is better
Bellman-Ford	O(nm)	Yes	- Detect negative weight cycle - Adjacency edge list is better
DAG-based	O(n+m)	Yes	- Graph must be acyclic - Adjacency edge list is better
Floyd- Warshall	O(n^3)	Yes (No negative-weight cycle)	- Good for dense graph - Adjacency matrix is better