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 / 5

In 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.

← Graphs & Graph Traversal