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
- Distance matrix: an $n \times n$ matrix holding direct arc costs between every pair of nodes.
- Labeled/unlabeled nodes: in Dantzig’s formulation, a node becomes “permanently labeled” once its shortest distance from the origin is finalized, mirroring the “visited” idea in Dijkstra’s algorithm.
- Node elimination: at each step, I select the unlabeled node with the smallest tentative distance and use it to update the distances of all remaining unlabeled nodes — effectively eliminating it from further consideration.
- Optimality principle: the same principle that underlies dynamic programming — the shortest path to any node must itself be composed of shortest sub-paths.
How It Works
- I build the initial cost matrix $C$ with direct arc costs, using $\infty$ for non-adjacent node pairs.
- I initialize the distance vector $d$ with $d(\text{origin}) = 0$ and $d(v) = c_{\text{origin},v}$ for all other nodes.
- I mark the origin as labeled (permanent).
- I select the unlabeled node $k$ with the minimum $d(k)$ and label it permanently.
- For every remaining unlabeled node $j$, I update $d(j) = \min(d(j), d(k) + c_{kj})$.
- 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.
- Initial: d = {O:0, A:3, B:6, C:∞}, labeled={O}
- Select A (min unlabeled, 3), label it. Update B: min(6, 3+2=5) → d[B]=5. Update C: min(∞, 3+7=10) → d[C]=10.
- Select B (min unlabeled, 5), label it. Update C: min(10, 5+1=6) → d[C]=6.
- Select C (min unlabeled, 6), label it. No unlabeled nodes remain.
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
- Naturally expressed using matrix operations, which makes it convenient for hand computation and for coupling with other matrix-based optimization techniques.
- Conceptually ties the shortest-path problem directly to linear programming, offering theoretical insight into duality and sensitivity analysis.
- Straightforward to implement for dense graphs represented as adjacency/cost matrices.
Disadvantages
- $O(n^2)$ performance is inefficient for large, sparse networks compared to heap-based Dijkstra implementations.
- Requires non-negative arc costs, same limitation as Dijkstra’s algorithm.
- The full matrix representation wastes memory on sparse graphs where most entries are $\infty$.
Applications
- Transportation and logistics network optimization, where Dantzig’s broader linear-programming toolkit was originally developed.
- Operations research coursework and textbook treatments connecting graph algorithms to LP duality.
- Network design and capacity planning where a matrix representation is already in use for other analyses.
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
- Convert the dense cost matrix into an adjacency list when the graph is sparse, reducing memory use and letting me apply a heap-based selection instead of a linear scan.
- Apply the same priority-queue optimization used in Dijkstra’s algorithm to bring the selection step down to $O(\log n)$.
- Precompute and cache repeated shortest-path queries if the same origin is queried multiple times against a static network.
Common Mistakes
- Treating “no direct arc” entries as zero instead of infinity, which silently creates false shortest paths.
- Re-scanning already-labeled nodes during the update step, wasting computation and risking incorrect overwrites.
- Applying the algorithm directly to graphs with negative arc costs, which breaks the same greedy assumption it shares with Dijkstra’s algorithm.
- Forgetting that this method assumes a complete or near-complete cost matrix, making it inefficient (though not incorrect) on very sparse graphs.
Further Reading
- Dantzig, G. B. (1963). Linear Programming and Extensions, Princeton University Press.
- Dantzig, G. B., Blattner, W., & Rao, M. R. (1967). “Finding a Cycle in a Graph with Minimum Cost to Time Ratio.” RAND Corporation.
- Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. Network Flows: Theory, Algorithms, and Applications, Prentice Hall.
- INFORMS biography of George Dantzig: https://www.informs.org/Explore/History-of-O.R.-Excellence/Biographical-Profiles/Dantzig-George-B
