Notes for Algorithms, Part II: Shortest Paths
Published at 2024-02-10Last update over 365 days agoLicensed under CC BY-NC-SA 4.0algorithmdata-structurecourseragraph-theoryspanning-treenoteThis is a note for 4.4 Shortest Paths, Algorithms, Part II.
Dijkstra's algorithm is essentially the same with Prim's algorithm. Both are in a family of algorithms that compute a graph's spanning tree (BTW, DFS and BFS are also in this family). The main distinction is the rule used to choose next vertex for the tree:
- Dijkstra's: Closest vertex to the source (via a directed path).
- Prim's: Closest vertex to the tree (via an undirected edge).