Guided Notes
Shortest Paths & Minimum Spanning Trees
Dijkstra's and Bellman-Ford shortest-path algorithms, and Prim's and Kruskal's minimum spanning trees.
The shortest path problem
Slide 1 / 5In a weighted graph, the shortest path between two vertices is the one with the smallest total edge weight — not necessarily the fewest edges.
It's the problem behind GPS navigation, network routing (how internet packets travel), flight planning, and games.
BFS only works when every edge costs the same. With weights, we need Dijkstra's or Bellman-Ford.