Offensive Security Researcher & Quantum Cryptography Analyst

Dantzig Shortest-Path Algorithm: Working, Explanation, and Applications

Abdul Wahab Junaid
Dantzig Shortest-Path algorithm and working of this algorithm

Dantzig Shortest-Path algorithm and working of this algorithm

I want to cover this algorithm because it represents one of the earliest formal treatments of the shortest-path problem, framed through the lens of linear programming and matrix operations rather than the graph-traversal style I use with Dijkstra’s or Bellman–Ford’s algorithms. George Dantzig’s shortest-path method finds the shortest paths between nodes in a network using an iterative matrix-based (or tableau-based) elimination procedure. I find it useful to know because it shows how the shortest-path problem connects directly to the broader field of linear and combinatorial optimization that Dantzig helped found.

History and Background

George Bernard Dantzig, best known as the inventor of the simplex method for linear programming, addressed the shortest-path problem in the 1960s as part of his broader work on network optimization. His approach, published in his influential book Linear Programming and Extensions (1963), presented the shortest-path problem as a special, highly structured case of a linear program, and offered an algorithm that systematically finds the shortest route by successively selecting the closest unlabeled node and updating a distance matrix — conceptually a close cousin of Dijkstra’s algorithm, developed independently and framed in matrix/optimization terms.

Problem Statement

I state it as: given a network of $n$ nodes represented by a distance (cost) matrix $C$, where $c_{ij}$ is the direct cost from node $i$ to node $j$ (and $\infty$ if no direct arc exists), find the minimum total-cost path from a designated origin node to every other node, using non-negative arc costs.

Core Concepts

How It Works

  1. I build the initial cost matrix $C$ with direct arc costs, using $\infty$ for non-adjacent node pairs.
  2. I initialize the distance vector $d$ with $d(\text{origin}) = 0$ and $d(v) = c_{\text{origin},v}$ for all other nodes.
  3. I mark the origin as labeled (permanent).
  4. I select the unlabeled node $k$ with the minimum $d(k)$ and label it permanently.
  5. For every remaining unlabeled node $j$, I update $d(j) = \min(d(j), d(k) + c_{kj})$.
  6. I repeat steps 4–5 until every node is labeled.

Working Principle

The mechanism is a greedy, matrix-driven generalization of the labeling idea: at each iteration I permanently fix the distance of the currently closest node, then use that node as a stepping-stone to potentially shorten the distances of everything still open. It works for the same underlying reason Dijkstra’s greedy step works — with non-negative costs, once a node has the smallest tentative distance among all unlabeled nodes, no future path through another unlabeled (and therefore farther) node could ever beat it.

Mathematical Foundation

I express the update rule as:

$$ d(j) = \min\big(d(j),\ d(k) + c_{kj}\big) \quad \text{for all unlabeled } j $$

where $k$ is the most recently labeled node. The problem can also be framed as the linear program:

$$ \min \sum_{(i,j) \in E} c_{ij} x_{ij} $$

subject to

$$ \sum_j x_{ij} – \sum_j x_{ji} = \begin{cases} 1 & i = \text{origin} \ -1 & i = \text{destination} \ 0 & \text{otherwise} \end{cases}, \qquad x_{ij} \geq 0 $$

This is the flow-conservation formulation Dantzig used to connect shortest paths to general linear programming, of which the labeling algorithm is a specialized, efficient solution method.

Diagrams

flowchart TD
    A([Start]) --> B["Build the cost matrix"]
    B --> C["Initialize the distance vector"]
    C --> D["Select the unlabeled node with the minimum distance"]
    D --> E["Mark the node as permanently labeled"]
    E --> F["Update distances of neighboring nodes"]
    F --> G{"Have all nodes been labeled?"}
    G -- No --> D
    G -- Yes --> H([Return the distance vector])

Pseudocode

function DantzigShortestPath(C, origin, n):
    for each node v:
        d[v] = C[origin][v]
    d[origin] = 0
    labeled = { origin }

    while |labeled| < n:
        k = the unlabeled node with minimum d[k]
        add k to labeled

        for each unlabeled node j:
            if d[k] + C[k][j] < d[j]:
                d[j] = d[k] + C[k][j]

    return d

Step-by-Step Example

Using the graph above with Origin, A, B, C and costs O→A=3, O→B=6, A→B=2, A→C=7, B→C=1.

Final distances from Origin: A=3, B=5, C=6.

Time Complexity

With a straightforward linear scan to find the minimum unlabeled distance at each step, the complexity is $O(n^2)$ for $n$ nodes, matching the matrix-based nature of the algorithm — this holds uniformly across best, average, and worst cases since I always scan the full matrix regardless of arrangement.

Space Complexity

I need $O(n^2)$ space to store the full cost matrix $C$, plus $O(n)$ for the distance vector and labeled-set tracking, giving total space $O(n^2)$, dominated by the matrix representation.

Correctness Analysis

The correctness argument mirrors Dijkstra’s: by induction, when a node $k$ is labeled, $d(k)$ already equals the true shortest distance, because any unexplored alternative path would have to pass through a still-unlabeled node whose distance is, by selection, no smaller than $d(k)$ — and since all costs are non-negative, that path cannot be shorter. This inductive argument holds at every step, so the final distance vector is optimal for all nodes.

Advantages

Disadvantages

Applications

Implementation in C

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

#define N 4  // number of nodes: 0=Origin, 1=A, 2=B, 3=C
#define INF INT_MAX

void dantzigShortestPath(int C[N][N], int origin) {
    int d[N];
    bool labeled[N] = { false };

    for (int v = 0; v < N; v++)
        d[v] = C[origin][v];
    d[origin] = 0;
    labeled[origin] = true;

    for (int count = 1; count < N; count++) {
        int k = -1, minDist = INF;
        for (int v = 0; v < N; v++) {
            if (!labeled[v] && d[v] < minDist) {
                minDist = d[v];
                k = v;
            }
        }
        if (k == -1) break;  // remaining nodes unreachable
        labeled[k] = true;

        for (int j = 0; j < N; j++) {
            if (!labeled[j] && C[k][j] != INF && d[k] != INF &&
                d[k] + C[k][j] < d[j]) {
                d[j] = d[k] + C[k][j];
            }
        }
    }

    printf("Node \t Distance from Origin\n");
    for (int v = 0; v < N; v++)
        printf("%d \t %d\n", v, d[v]);
}

int main() {
    int C[N][N] = {
        {0,   3,   6,   INF},
        {INF, 0,   2,   7},
        {INF, INF, 0,   1},
        {INF, INF, INF, 0}
    };

    dantzigShortestPath(C, 0);
    return 0;
}

Sample Input and Output

Input: the cost matrix above, origin node 0.

Output:

Node     Distance from Origin
0        0
1        3
2        5
3        6

This matches my manual walkthrough.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version