Option · Module
Algorithms on graphs II
Dijkstra'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 minRoute inspection and TSP
To travel every edge and return, you must repeat edges between odd vertices. Pair the odd vertices to minimise the extra distance; route length total weight that extra. For visiting every vertex (TSP), bound the answer: nearest neighbour gives an upper bound; deleted vertex (MST of the rest two cheapest edges) gives a lower bound.
≈ 45 min