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.