Shortest Path Algorithms from Scratch (2026)
Shortest path algorithms are fundamental to graph theory, determining the minimal distance between nodes in a weighted graph. Dijkstra, Bellman-Ford, and Floyd-Warshall each serve distinct use cases with different trade-offs.
Dijkstra's algorithm handles non-negative weights efficiently using a priority queue, Bellman-Ford detects negative cycles through iterative relaxation, and Floyd-Warshall computes all-pairs shortest paths via dynamic programming.
Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path from a source to all vertices using a greedy approach. It maintains a priority queue of vertices ordered by their current distance and relaxes edges from the closest unprocessed vertex.
The algorithm runs in O((V+E) log V) with a binary heap and fails on negative weight edges because it assumes earlier settled distances are final.
vector dijkstra(vector>>& graph, int src) {
int V = graph.size();
vector dist(V, INT_MAX);
dist[src] = 0;
priority_queue, vector>, greater<>> pq;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : graph[u])
if (dist[u] + w < dist[v])
dist[v] = dist[u] + w, pq.push({dist[v], v});
}
return dist;
} Bellman-Ford Algorithm
Bellman-Ford iteratively relaxes all edges V-1 times to guarantee shortest paths. A final pass detects negative cycles reachable from the source.
Its O(VE) complexity makes it slower than Dijkstra, but it handles negative weights and cycle detection, making it essential for general-purpose shortest path problems.
vector bellmanFord(int V, vector>& edges, int src) {
vector dist(V, INT_MAX);
dist[src] = 0;
for (int i = 0; i < V - 1; i++)
for (auto& e : edges)
if (dist[e[0]] != INT_MAX && dist[e[0]] + e[2] < dist[e[1]])
dist[e[1]] = dist[e[0]] + e[2];
for (auto& e : edges)
if (dist[e[0]] != INT_MAX && dist[e[0]] + e[2] < dist[e[1]])
return {}; // negative cycle
return dist;
} Floyd-Warshall Algorithm
Floyd-Warshall computes shortest paths between all pairs using a 2D DP matrix. For each intermediate vertex k, it checks whether path i->k->j is shorter than i->j.
With O(V³) time, it is ideal for dense graphs or when all-pairs distances are needed, and it can detect negative cycles by checking diagonal entries.
vector> floydWarshall(vector>& graph) {
int V = graph.size();
vector> dist = graph;
for (int k = 0; k < V; k++)
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
return dist;
} Frequently Asked Questions
When should I use Dijkstra over Bellman-Ford?
Use Dijkstra when all edge weights are non-negative and you need better O((V+E) log V) performance. Use Bellman-Ford when negative weights exist or you need to detect negative cycles.
Can Floyd-Warshall handle negative weights?
Yes, Floyd-Warshall handles negative weights and detects negative cycles, but it does not work with negative cycles in the shortest path computation as distances become -infinity.
Originally published on Ayodhyyya. Last updated June 1, 2026.