L18 Slides

We discussed a slight modification to Prim’s algorithm which results in Dijkstra’s algorithm; we discussed why the algorithm is correct, and a simplification of the algorithm: when edge weights are all 1, then the algorithm simplifies to breadth-first search, which returns the shortest number of edges from a source node s to every other node in the graph.