Offensive Security Researcher & Quantum Cryptography Analyst

Ford’s Shortest-Path Algorithm: Working, Explanation, and Applications

Abdul Wahab Junaid
Ford's Shortest-Path algorithm and working of this algorithm

Ford's Shortest-Path algorithm and working of this algorithm

I want to introduce this algorithm as the one I reach for whenever Dijkstra’s algorithm isn’t good enough — specifically, whenever my graph has negative edge weights. Ford’s shortest-path algorithm, more commonly known today as the Bellman–Ford algorithm, finds the shortest path from a single source to all other vertices in a weighted graph, and it can also detect if the graph contains a negative-weight cycle. I find this dual capability — solving shortest paths and catching a structurally impossible situation — is what makes it distinct and important.

History and Background

The algorithm was developed by Lester Randolph Ford Jr., who published the underlying method in 1956 as part of his work on network flow theory. Richard Bellman, working independently, formalized and popularized it in 1958 in the context of dynamic programming, which is why the algorithm today most often carries both names. I think of it as one of the earliest and clearest applications of dynamic programming to graph problems, predating even Dijkstra’s more famous algorithm by a few years in its original conception.

Problem Statement

I define the problem as: given a weighted, directed graph $G = (V, E)$ where edge weights may be negative (but the graph must not contain a negative-weight cycle reachable from the source for the shortest paths to be well-defined), and a source vertex $s$, I want to compute the shortest distance from $s$ to every other vertex, or correctly report that a negative cycle makes some distances undefined.

Core Concepts

How It Works

  1. I initialize the distance to the source as 0 and to every other vertex as infinity.
  2. I repeat the following $|V| – 1$ times: for every edge $(u, v)$ with weight $w$, if $dist[u] + w < dist[v]$, I update $dist[v] = dist[u] + w$.
  3. After these passes, I perform one more pass over all edges. If any edge can still be relaxed (its endpoint distance would still decrease), I know the graph contains a negative-weight cycle reachable from the source, and I report that instead of a “correct” shortest-path answer.

Working Principle

The underlying logic is dynamic programming: I let $dist_k(v)$ represent the shortest path to $v$ using at most $k$ edges. Each full pass over all edges effectively computes $dist_k$ from $dist_{k-1}$ for every vertex simultaneously. Since any shortest simple path has at most $|V|-1$ edges, after $|V|-1$ passes I am guaranteed to have found the true shortest distances — assuming no negative cycle exists. The extra final pass is my safety check: if distances are still improving after $|V|-1$ rounds, something is looping negatively.

Mathematical Foundation

I formalize the relaxation step identically to Dijkstra’s:

$$ dist[v] = \min\big(dist[v],\ dist[u] + w(u,v)\big) $$

The dynamic programming recurrence across passes is:

$$ dist_k(v) = \min\Big(dist_{k-1}(v),\ \min_{(u,v) \in E}\big(dist_{k-1}(u) + w(u,v)\big)\Big) $$

with $dist_0(s) = 0$ and $dist_0(v) = \infty$ for $v \neq s$. The negative-cycle detection condition after the $(|V|-1)$-th pass is:

$$ \exists (u,v) \in E : dist[u] + w(u,v) < dist[v] $$

If this holds, no finite shortest path exists for at least one vertex.

Diagrams

flowchart TD
    Start([Start]) --> Init[dist=0 for source, infinity for rest]
    Init --> Pass["Repeat |V|-1 times: relax every edge"]
    Pass --> Check{Any edge still relaxable?}
    Check -- Yes --> Neg[Report negative-weight cycle]
    Check -- No --> Done[Return dist as shortest paths]

Pseudocode

function BellmanFord(Graph, source):
    for each vertex v in Graph:
        dist[v] = infinity
        prev[v] = undefined
    dist[source] = 0

    for i from 1 to |V| - 1:
        for each edge (u, v) with weight w in Graph:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u

    // Check for negative-weight cycles
    for each edge (u, v) with weight w in Graph:
        if dist[u] + w < dist[v]:
            report "Graph contains a negative-weight cycle"
            return

    return dist[], prev[]

Step-by-Step Example

Using the graph above with source A: edges A→B(4), A→C(5), B→C(−3), C→D(2), B→D(4). Here $|V|=4$, so I need 3 passes.

Final shortest distances from A: B=4, C=1, D=3.

Time Complexity

Each of the $|V|-1$ passes scans every edge, giving $O(V \cdot E)$ overall — this is the same for best, average, and worst case, since the algorithm always performs the full number of passes regardless of input (unless I add an early-exit optimization when no edge is relaxed in a pass).

Space Complexity

I need $O(V)$ space for the distance and predecessor arrays, plus $O(V+E)$ for the edge list representation of the graph, giving total space $O(V+E)$.

Correctness Analysis

The correctness proof relies on the fact that a shortest simple path in a graph with no negative cycle contains at most $|V|-1$ edges — because a simple path visits each vertex at most once. By induction on the number of passes, after pass $k$, $dist[v]$ correctly holds the shortest distance to $v$ using at most $k$ edges. After $|V|-1$ passes, this covers all possible shortest simple paths, so $dist[v] = \delta(s,v)$ for every reachable vertex. The negative-cycle check works because if a negative cycle exists, distances along it can be decreased indefinitely, so an edge on or reachable from that cycle will always be relaxable no matter how many passes I run.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <limits.h>

#define V 4
#define E 5

struct Edge {
    int src, dest, weight;
};

void bellmanFord(struct Edge edges[], int src) {
    int dist[V];
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;

    // Relax all edges |V| - 1 times
    for (int i = 1; i <= V - 1; i++) {
        for (int j = 0; j < E; j++) {
            int u = edges[j].src;
            int v = edges[j].dest;
            int w = edges[j].weight;
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // Check for negative-weight cycles
    for (int j = 0; j < E; j++) {
        int u = edges[j].src;
        int v = edges[j].dest;
        int w = edges[j].weight;
        if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
            printf("Graph contains a negative-weight cycle\n");
            return;
        }
    }

    printf("Vertex \t Distance from Source\n");
    for (int i = 0; i < V; i++)
        printf("%d \t %d\n", i, dist[i]);
}

int main() {
    // 0=A, 1=B, 2=C, 3=D
    struct Edge edges[E] = {
        {0, 1, 4},   // A->B
        {0, 2, 5},   // A->C
        {1, 2, -3},  // B->C
        {2, 3, 2},   // C->D
        {1, 3, 4}    // B->D
    };

    bellmanFord(edges, 0);
    return 0;
}

Sample Input and Output

Input: the edge list above, source vertex A (index 0).

Output:

Vertex   Distance from Source
0        0
1        4
2        1
3        3

This matches my manual pass-by-pass walkthrough exactly.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version