4.3.6.1 - Dijkstra's shortest-path algorithm (VB.NET)

Tentative distances and fixed vertices

Dijkstra's algorithm keeps the best distance found so far to every vertex and repeatedly fixes the smallest unsettled distance.

Use nonnegative edge weights. They might represent travel time, distance or cost. The start has tentative distance 0; every other vertex begins at infinity, meaning no route has yet been found. A fixed vertex has its final shortest distance. Its distance cannot later improve because every unfinished route starts at a tentative distance at least as large, then adds nonnegative cost.

Use these supplied steps for all the traces in this lesson:

1. Initialise distances as above, every vertex unfixed and every predecessor absent.
2. Choose the unfixed vertex with the smallest finite tentative distance. Break a tie alphabetically. If none exists, stop: remaining vertices are unreachable.
3. Fix that vertex. For each unfixed neighbour, calculate the chosen vertex's distance plus the connecting edge weight.
4. If this candidate is smaller than the neighbour's current distance, replace the distance and set its predecessor to the chosen vertex. On an equal cost, keep the existing predecessor.
5. Repeat from step 2. To answer only for one destination, it is sufficient to stop when that destination is fixed, rather than when it is first discovered.

Negative edge weights invalidate this guarantee. Infinity is a sentinel for no known route, not a large actual journey cost.

Relaxing weighted edges and tracing source

Relaxing an edge tests whether a route through the current vertex improves the best distance recorded for its neighbour.

[DIAGRAM: asset_slug: shortest_path_graph; description: Exact weighted graph for the A-to-E shortest-path trace]

The graph is undirected, with edges A–B=4, A–C=1, B–C=2, B–D=1, C–D=5, B–E=7 and D–E=3. Starting at A gives this complete trace; ∞ means no route has yet been found.

For example, C improves B from 4 to $1+2=3$. B then improves D from 6 to $3+1=4$. A vertex's first discovered route need not be its final shortest route.

This supplied VB.NET implementation uses a square adjacency matrix, vertices indexed from 0, -1 for no edge and nonnegative integers for actual weights. The matrix has at least one vertex, the start is valid, and every edge weight and finite shortest-path cost is below 1,000,000. A linear scan chooses the next vertex; strict comparison breaks ties by the smallest index. Put it inside a module.

Function ShortestPaths(weights As Integer(,), start As Integer,
                       ByRef previous As Integer()) As Integer()
    Const Infinity As Integer = 1000000
    Dim n As Integer = weights.GetLength(0)
    Dim distance(n - 1) As Integer
    Dim fixedNode(n - 1) As Boolean
    ReDim previous(n - 1)
    For i As Integer = 0 To n - 1
        distance(i) = Infinity
        previous(i) = -1
    Next
    distance(start) = 0
    For round As Integer = 0 To n - 1
        Dim current As Integer = -1
        Dim best As Integer = Infinity
        For i As Integer = 0 To n - 1
            If Not fixedNode(i) AndAlso distance(i) < best Then
                current = i
                best = distance(i)
            End If
        Next
        If current = -1 Then Exit For
        fixedNode(current) = True
        For neighbour As Integer = 0 To n - 1
            If Not fixedNode(neighbour) AndAlso weights(current, neighbour) >= 0 Then
                Dim candidate As Integer = distance(current) + weights(current, neighbour)
                If candidate < distance(neighbour) Then
                    distance(neighbour) = candidate
                    previous(neighbour) = current
                End If
            End If
        Next
    Next
    Return distance
End Function