no> [!summary] Finding the shortest path between a pair of vertices.
| Condition | Algorithm | Time Complexity |
|---|---|---|
| Unweighted Graph | BFS | |
| No Negative Weight Cycles | Bellman-Ford | |
| No Negative Weights | Dijkstra’s | depends.. |
| Tree | BFS/DFS | |
| Directed Acyclic Graph | DAG SSSP |
DAG SSSP
This algorithm
- does a topological sort on the graph, while relaxing the edges.
- now, in topological order, each vertex is processed.
This works for DAGs because of the property that at vertex v, all the shortest paths to all its parents have been found.
→ E (3)