Shortest Path Algorithms

• Dijkstra's algorithm finds the shortest distance from one fixed start vertex to every other vertex in a network (or you can stop early once you hit your target vertex).
• Each vertex gets a labelling box with four values: the vertex name, its order of being finalised, its final (permanent) shortest distance, and its running "working values."
• You build up the network by only ever looking at neighbours of the most recently finalised vertex, and you always keep the smallest working value seen so far.
• Once every vertex (or your target) has a final label, you trace the shortest route backwards from the destination using the "difference in final labels = edge weight" trick.
• Floyd's algorithm finds the shortest distance between every pair of nodes in a network — not just from one starting point — using two matrices: a distance matrix and a route matrix.
• Floyd's algorithm updates both matrices in a fixed number of iterations (one per node), each time checking whether going "via" a particular node gives a shorter route.
• Dijkstra = fast, but only from one start point. Floyd = slower, but gives you the whole picture for any start/end pair. Repeating Dijkstra from every possible start vertex would eventually give you the same information as one full run of Floyd's algorithm.

every single

grows outward like ripples on a pond every