Comparing Dijkstra's & Floyd's Algorithms (Edexcel A Level Further Maths: Decision 1): Revision Note

Comparing Dijkstra's & Floyd's algorithms

What is the difference between Dijkstra's and Floyd's algorithms?

• Both algorithms find the shortest path, and its weight (length) between nodes on a graph

• Dijkstra's algorithm finds the shortest path between a fixed starting node and every other node in the network

  • This would be useful where a starting point cannot be moved

    • e.g.  a power station, a distribution warehouse

  • The advantage of Dijkstra's algorithm are speed

    • the algorithm can be stopped once the desired end node is reached

  • The disadvantage of Dijkstra's algorithm is the limited information it provides (compared to Floyd's)

• Floyd's algorithm finds the shortest path between any pair of start and end nodes

  • This would be useful where a starting point can be anywhere on the network

    • e.g. a robot inspecting a network of pipelines

  • The advantage of Floyd's algorithm is the amount of information it provides (compared to Dijkstra)

  • The disadvantage of Floyd's algorithm is the time it takes (especially manually without a computer!)

• Repeating Dijkstra's algorithm, taking each node in turn as the starting node, would produce the same information as Floyd's algorithm