Both Dijkstra’s Algorithm and Floyd’s Algorithm (Floyd–Warshall Algorithm) are used to find shortest paths in a network or graph, but they differ in purpose, scope, and process.
Here’s a clear comparison:
1. Dijkstra’s Algorithm
Used when you only care about the shortest route from one specific node.
Example: Find the shortest path from City A to all other cities.
It repeatedly selects the nearest unvisited node and updates distances.
Basic Idea
- Start from source node.
- Assign tentative distances.
- Choose nearest unvisited node.
- Relax/update neighboring distances.
- Repeat until all nodes are visited.
Example Use Cases
- GPS navigation
- Network routing
- Delivery optimization
2. Floyd’s Algorithm (Floyd–Warshall)
Used when you need shortest paths between every pair of nodes.
Example: Find the shortest distance between every city and every other city.
It checks whether passing through an intermediate node gives a shorter route.
Core Formula
Meaning:
- Current shortest path from i to j
- versus
- Path from i to k plus k to j
Choose the smaller one.
Example Use Cases
- Airline route systems
- Network analysis
- Traffic systems
- Social network connections
Simple Analogy
Imagine cities connected by roads.
Dijkstra
“From Manila, what is the shortest route to every other city?”
Only one starting point.
Floyd-Warshall
“What is the shortest route between EVERY pair of cities?”
All cities compared with all others.
Key Difference in One Sentence
- Dijkstra = shortest path from one node
- Floyd = shortest paths between all nodes
Which One Should You Use?
Use Dijkstra when:
- You only need one source node
- Graph is large and sparse
- Edge weights are non-negative
Use Floyd–Warshall when:
- You need all-pairs shortest paths
- Graph is relatively small
- Negative edges may exist (without negative cycles)