Shortest Paths: Dijkstra & Bellman–Ford · Algorithms (DAA)

Given a weighted graph and a source vertex s, find the shortest-path distance from s to every other vertex. (BFS solves this only when all edges have the same weight.)

Relaxation

Both algorithms repeatedly relax edges. For an edge u → v with weight w:

Pseudocode

RELAX(u, v, w)
    if dist[u] + w < dist[v]
        dist[v] = dist[u] + w
        parent[v] = u

"If going through u gives a shorter route to v, use it."

Dijkstra's algorithm

Greedy rule: repeatedly pick the unvisited vertex with the smallest known distance, mark it final, and relax its outgoing edges. Works when all edge weights are non-negative.

A directed weighted graph. The shortest path S → B → A → C → T has length 3 + 4 + 2 + 4 = 13.

C++

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <string>
using namespace std;

int main() {
    const string name = "SABCDT";
    int V = 6;
    vector<vector<pair<int, int>>> adj(V);
    int e[][3] = {{0,1,10},{0,2,3},{2,1,4},{1,3,2},{2,4,8},{2,3,9},{3,5,4},{4,5,5},{3,4,1}};
    for (auto &x : e) adj[x[0]].push_back({x[1], x[2]});

    vector<int> dist(V, INT_MAX), parent(V, -1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;   // (distance, vertex)
    dist[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;                         // outdated entry
        cout << "finalise " << name[u] << " at distance " << d << endl;
        for (auto [v, w] : adj[u])
            if (dist[u] + w < dist[v]) {                   // relax
                dist[v] = dist[u] + w;
                parent[v] = u;
                pq.push({dist[v], v});
            }
    }
    string path;
    for (int v = 5; v != -1; v = parent[v]) path = string(1, name[v]) + (path.empty() ? "" : " -> ") + path;
    cout << "shortest S to T: " << dist[5] << " via " << path << endl;
    return 0;
}

Output

finalise S at distance 0
finalise B at distance 3
finalise A at distance 7
finalise C at distance 9
finalise D at distance 10
finalise T at distance 13
shortest S to T: 13 via S -> B -> A -> C -> T

Try it Yourself

Time with a binary heap: O((V + E) log V).

Bellman–Ford

Relax every edge, V − 1 times. After round k, every shortest path using at most k edges is correct, and a shortest path never needs more than V − 1 edges. A V-th round that still improves some distance proves a negative cycle is reachable (no shortest path exists).

C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct Edge { int u, v, w; };

void bellmanFord(int V, const vector<Edge> &edges, int src) {
    vector<long> dist(V, LONG_MAX);
    dist[src] = 0;
    for (int round = 1; round < V; round++)
        for (const Edge &e : edges)
            if (dist[e.u] != LONG_MAX && dist[e.u] + e.w < dist[e.v]) dist[e.v] = dist[e.u] + e.w;
    for (const Edge &e : edges)
        if (dist[e.u] != LONG_MAX && dist[e.u] + e.w < dist[e.v]) { cout << "negative cycle detected!" << endl; return; }
    for (int v = 0; v < V; v++) cout << "dist[" << v << "] = " << dist[v] << endl;
}

int main() {
    vector<Edge> g1 = {{0,1,6},{0,2,7},{1,2,8},{1,3,5},{1,4,-4},{2,3,-3},{2,4,9},{3,1,-2},{4,0,2},{4,3,7}};
    bellmanFord(5, g1, 0);
    cout << "---" << endl;
    vector<Edge> g2 = {{0,1,1},{1,2,-1},{2,3,-1},{3,1,-1}};      // cycle 1 -> 2 -> 3 -> 1 has weight -3
    bellmanFord(4, g2, 0);
    return 0;
}

Output

dist[0] = 0
dist[1] = 2
dist[2] = 7
dist[3] = 4
dist[4] = -2
---
negative cycle detected!

Try it Yourself

Time: O(V · E) — slower than Dijkstra but handles negative weights.

Comparison

	BFS	Dijkstra	Bellman–Ford	Floyd–Warshall
Edge weights	all equal	non-negative	any (detects negative cycles)	any (no negative cycles)
Sources	single	single	single	all pairs
Time	O(V + E)	O((V + E) log V)	O(VE)	O(V³)
Technique	traversal	greedy	dynamic programming	dynamic programming

Test yourself

4 questions · pick an answer to check it instantly

1
What condition must edge weights satisfy for Dijkstra's algorithm to be correct?
2
How many rounds of relaxing all edges does Bellman–Ford perform before the cycle check?
3
How does Bellman–Ford detect a negative cycle?
4
What is the time complexity of Dijkstra with a binary heap?

#Relaxation

#Dijkstra's algorithm

#Bellman–Ford

#Comparison

Test yourself

Relaxation

Dijkstra's algorithm

Bellman–Ford

Comparison