4.3.6.1 - Dijkstra's shortest-path algorithm (C#)

Tentative distances and visited nodes

Dijkstra's algorithm finds shortest paths from a starting vertex in a graph with non-negative edge weights. A path's cost is the sum of its edge weights; the path with the fewest edges need not have the least cost.

Use this supplied algorithm. “Finalised” is often called “visited” in Dijkstra questions; here it means selected for processing, rather than merely discovered.

1. Give the start distance 0 and every other distance infinity; all vertices are unfinalised and have no predecessor.
2. Select an unfinalised vertex with the smallest finite tentative distance. If there is none, stop.
3. For each unfinalised neighbour, calculate current distance plus edge weight. If this is smaller than its stored distance, replace that distance and record the current vertex as predecessor.
4. Finalise the current vertex and repeat. Stop once every reachable vertex is finalised, or once the requested destination is finalised.

Equal smallest distances can be resolved using a stated tie rule. Infinity means not yet reached, not a huge real path cost. A disconnected vertex remains infinity. Negative edges break the guarantee that no later path can improve a finalised distance, so this algorithm's guarantee excludes them.

This weighted undirected graph will be used throughout the worked trace. Edges not listed do not exist.

[DIAGRAM: asset_slug: dijkstra-network; description: Exact weighted undirected network A–B 4, A–C 1, B–C 2, B–D 1, C–D 5, C–E 9 and D–E 3.]

Relaxing weighted edges

Relaxation means checking whether a route through the current vertex improves a neighbour's known distance. A newly found route replaces a distance only when it is smaller; do not overwrite a better route simply because another edge is examined.

Starting at A, the supplied algorithm produces this state after each selected vertex's neighbours have been considered. Brackets show the predecessor; a dash means none.

After A, C's distance 1 is smaller than B's 4, so C is next. Via C, B improves to 1+2=3. Via B, D improves from 6 to 3+1=4. Via D, E improves from 10 to 4+3=7. Distances can improve before finalisation; the selection order is A, C, B, D, E.

The following complete static C# program implements the supplied steps. Vertices A–E are indices 0–4. A matrix value -1 means no edge, allowing an actual zero-weight edge. Guaranteed finite path totals fit an int. The finite-distance selection guard prevents adding a weight to the infinity sentinel.

using System;
class Program
{
    static void Main()
    {
        int[,] weights = {
            { -1, 4, 1, -1, -1 }, { 4, -1, 2, 1, -1 },
            { 1, 2, -1, 5, 9 }, { -1, 1, 5, -1, 3 },
            { -1, -1, 9, 3, -1 }
        };
        int n = weights.GetLength(0);
        int[] distance = new int[n];
        int[] predecessor = new int[n];
        bool[] finalised = new bool[n];
        for (int v = 0; v < n; v++)
        {
            distance[v] = int.MaxValue;
            predecessor[v] = -1;
        }
        distance[0] = 0;
        for (int step = 0; step < n; step++)
        {
            int current = -1;
            for (int v = 0; v < n; v++)
                if (!finalised[v] && distance[v] != int.MaxValue &&
                    (current == -1 || distance[v] < distance[current]))
                    current = v;
            if (current == -1) break;
            for (int next = 0; next < n; next++)
                if (!finalised[next] && weights[current, next] >= 0)
                {
                    int candidate = distance[current] + weights[current, next];
                    if (candidate < distance[next])
                    {
                        distance[next] = candidate;
                        predecessor[next] = current;
                    }
                }
            finalised[current] = true;
        }
        Console.WriteLine(distance[4]);
    }
}