Round 8: Graphs, part II

In this round, we continue on graph algorithms. We now consider edge-weighted graphs that appear in many applications and show how some elementary problems on them can be solved algorithmically.

Contents:

• Edge-weighted graphs
• Minimum spanning trees
• Single-source shortest paths

Material in Introduction to Algorithms (Aalto access):

• ​ Minimum spanning trees: Chapter 21

• ​ Single-source shortest paths: Chapter 22

Some external links:

• ​ MIT 6.006 OCW video on single-source shortest paths

• ​ MIT 6.006 OCW video on Dijkstra’s algorithm

• ​ MIT 6.006 OCW video on Bellman-Ford

• ​ A visualization of Kruskal’s algorithm

• ​ A visualization of Prim’s algorithm

• ​ A visualization of Dijkstra’s algorithm