Shortest paths: Dijkstra and Floyd–Warshall

Introduction

On a weighted graph, the shortest path is the one with the smallest total weight, not the fewest edges: a long road with no traffic can beat a short one. BFS no longer works; these two algorithms do.

Roads, flight prices and network links all carry a cost, and the cheapest route is rarely the one with the fewest hops. These algorithms find it, and they make a good contrast between a greedy method and a dynamic program.

How it works

Dijkstra's algorithm

#include <stdio.h>
#define N 5
#define INF 1000000

int main(void) {
    int w[N][N] = {   // w[u][v] = edge weight, 0 = no edge
        {0, 4, 1, 0, 0},
        {4, 0, 2, 5, 0},
        {1, 2, 0, 8, 10},
        {0, 5, 8, 0, 2},
        {0, 0, 10, 2, 0},
    };
    int dist[N], done[N];
    for (int i = 0; i < N; i++) {
        dist[i] = INF;
        done[i] = 0;
    }
    dist[0] = 0;
    for (int round = 0; round < N; round++) {
        int u = -1;
        for (int i = 0; i < N; i++)   // the closest vertex that is not done
            if (!done[i] && (u == -1 || dist[i] < dist[u])) u = i;
        done[u] = 1;
        for (int v = 0; v < N; v++)   // relax u's edges
            if (w[u][v] && dist[u] + w[u][v] < dist[v])
                dist[v] = dist[u] + w[u][v];
    }
    for (int i = 0; i < N; i++) printf("0 -> %d: %d\n", i, dist[i]);
    return 0;
}

Dijkstra finds the shortest distance from one start vertex to every other vertex, when no weight is negative. It is greedy:

1. dist[start] = 0, every other dist is infinity (INF).
2. Pick the vertex u with the smallest dist that is not done yet, and mark it done: its distance is now final.
3. Relax each edge u → v: if going through u is shorter, dist[v] = dist[u] + w[u][v].
4. Repeat until every vertex is done.

Watch dist shrink: vertex 1 is first reached at 4 (directly), then improved to 3 through vertex 2.

This version scans for the closest vertex each round, so it is O(n²), which is good for dense graphs. With a min-heap of (dist, vertex) pairs, it becomes O((n + m) log n).

Negative weights break it: a vertex marked done might later be reached more cheaply through a negative edge. The Bellman–Ford algorithm handles negative weights by relaxing every edge n - 1 times, in O(n × m).

Syntax

if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;           // relax one edge

for (k) for (i) for (j)                                     // Floyd–Warshall
    if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];

Example

#include <stdio.h>
#define N 4
#define INF 99999

int main(void) {
    int d[N][N] = {   // directed edges; INF = no edge
        {0, 5, INF, 10},
        {INF, 0, 3, INF},
        {INF, INF, 0, 1},
        {INF, INF, INF, 0},
    };
    for (int k = 0; k < N; k++)
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (d[i][j] == INF) printf("  INF");
            else printf("%5d", d[i][j]);
        }
        printf("\n");
    }
    return 0;
}

To get the distance between every pair of vertices, Floyd–Warshall tries each vertex k in turn as a stop on the way: is i → k → j shorter than the best i → j so far?

Three nested loops over n vertices: O(n³). It is short to write, handles negative edges (but not negative cycles), and is a dynamic program: after step k, d[i][j] is the shortest path using only stops 0 .. k.

Line by line

1. d starts as the direct distances: 0 on the diagonal, and INF where there is no edge.
2. The outer loop picks k, the vertex now allowed as a stop on the way.
3. The two inner loops try every pair i, j.
4. If going through k is shorter than the best known route, d[i][j] is updated.
5. INF is small enough that INF + INF still fits in an int, so the comparison cannot overflow.
6. The final loops print the matrix, writing INF for any pair with no route.

Expected result

    0    5    8    9
  INF    0    3    4
  INF  INF    0    1
  INF  INF  INF    0

In the real world

Link-state internet routing protocols such as OSPF run Dijkstra's algorithm inside each router. Map services use it too, in versions with extra preprocessing so that they can answer in milliseconds on a whole continent.

Common mistakes

• Using a huge INF like INT_MAX: INF + w overflows. Use a value much larger than any real path but far from the int limit.
• In Floyd–Warshall, putting the k loop inside the i and j loops. It must be the outer loop.
• Marking a vertex as finished in Dijkstra before choosing the smallest unfinished distance.

Best practices

• Pick the algorithm by asking three things: one source or every pair, any negative edges, and how large the graph is.
• Store a parent for each vertex if you need the route as well as its length.
• Test with an unreachable vertex.

Summary

Shortest-path algorithms repeatedly relax edges. Dijkstra greedily finalises the nearest vertex and needs non-negative weights, Bellman–Ford allows negative ones, and Floyd–Warshall computes all pairs in O(n³).

Mark lesson complete