WDM11 · Module
Algorithms on graphs
Kruskal's and Prim's algorithms
A minimum spanning tree (MST) connects every vertex with the least total weight and no cycles; it has edges. Kruskal adds the cheapest remaining edge unless it makes a cycle. Prim grows one tree, always adding the cheapest edge from the tree to a new vertex, and works directly on a distance matrix.
≈ 40 minDijkstra's and Floyd's algorithms
Dijkstra's algorithm finds the shortest route from one start vertex: give each vertex a working value, permanently label the smallest, update its neighbours, repeat. Trace back using edges where label difference equals edge weight. Floyd's algorithm finds shortest distances between every pair using a table, one vertex at a time.
≈ 45 min