Pages
▼
Graph Algorithms Complexity
| Algorithm | Time Complexity | Space Complexity |
|---|
| Average | Worst | Worst |
|---|
| Dijkstra's algorithm | O(|E| log |V|) | O(|V|^2) | O(|V| + |E|) |
| A* search algorithm | O(|E|) | O(b^d) | O(b^d) |
| Prim's algorithm | O(|E| log |V|) | O(|V|^2) | O(|V| + |E|) |
| Bellman–Ford algorithm | O(|E| ⋅ |V|) | O(|E| ⋅ |V|) | O(|V|) |
| Floyd-Warshall algorithm | O(|V|^3) | O(|V|^3) | O(|V|^2) |
| Topological sort | O(|V| + |E|) | O(|V| + |E|) | O(|V| + |E|) |
