Comparison of Dijkstra, Bellman-Ford, and Floyd-Warshall Algorithms
Feature Dijkstra Bellman-Ford Floyd-Warshall
Finds shortest path
Finds the shortest
from a single source Finds shortest paths
path from a single
Purpose to all other vertices, between all pairs of
source to all other
even with negative vertices.
vertices.
weights.
Weighted graph, Weighted graph,
Weighted graph with
including graphs with including graphs with
Graph Type non-negative
negative weights (no negative weights (no
weights.
negative cycles). negative cycles).
O(VE), where V is
O(V^2) or O(E + V
the number of
Time Complexity log V) with a priority O(V^3).
vertices and E is the
queue (binary heap).
number of edges.
Dynamic Dynamic
Algorithm Type Greedy
Programming Programming
Negative Weight
Not supported. Supported. Supported.
Edges
Detects and reports Cannot handle graphs
Negative Weight Not handled; the
negative weight with negative weight
Cycles algorithm may fail.
cycles. cycles.
Space Complexity O(V). O(V). O(V^2).
Shortest path from
Shortest path from the source to all Shortest paths
Result the source to all vertices or detection between all pairs of
vertices. of negative weight vertices.
cycles.
Efficient for large Useful when negative Used for dense
graphs with weights exist and graphs or when
Usage Scenarios
non-negative cycle detection is all-pairs shortest
weights. needed. paths are required.
