Shortest Path Algorithms (Edexcel A-Level Further Mathematics): Revision Notes
📚 Revision Notes
10.4.3 Comparing Dijkstra's & Floyd's Algorithms
Dijkstra's and Floyd's algorithms are both used to find shortest paths in a graph, but they differ in purpose, approach, and application. Understanding these differences can help determine which algorithm to use in a given scenario.
Key Differences
Purpose
- Dijkstra's Algorithm: Finds the shortest path from a single source node to all other nodes in the graph.
- Floyd's Algorithm: Finds the shortest paths between all pairs of nodes in the graph.
Approach
- Dijkstra's Algorithm: Uses a greedy approach, iteratively selecting the closest unvisited node and updating its neighbours' distances.
- Floyd's Algorithm: Uses a dynamic programming approach, iteratively considering each node as an intermediate step to update the shortest paths between all pairs.
Graph Type
- Both algorithms work on directed and undirected graphs, provided there are no negative weight cycles. However, Dijkstra's is more sensitive to negative edge weights.
Use Cases
- Use Dijkstra's for routing from a single source, such as navigation or network routing.
- Use Floyd's for analysing the shortest paths between multiple nodes, such as transportation networks or communication analysis.
Note Summary
infoNote
Common Mistakes
- Confusing the Purposes: Using Floyd's algorithm when only a single-source shortest path is required, or Dijkstra's when all-pairs shortest paths are needed.
- Applying to Graphs with Negative Cycles: Neither algorithm can handle graphs with negative weight cycles.
- Inefficient Use: Applying Dijkstra's algorithm repeatedly for all-pairs shortest paths instead of using Floyd's, leading to unnecessary computation.
- Ignoring Edge Weights: Treating edges as unweighted in problems where weights are critical to the solution.
infoNote
Key Formulas/Theorems
- Dijkstra's Tentative Distance Update:
- Floyd's Distance Update: