The following implementation of Dijkstra’s shortest path finding algorithm employs a class by the name of Dijkstra.

Public Class Dijkstra

    Private aShortestDistances() As Double
    Private aPreviousVertices() As Double
    Private unvisitedVertices As New List(Of Integer)

    Public Sub New(adjacencyMatrix As Double(,), totalVertices As Integer)

        'Initialise the shortest distances array and the list of unvisited vertices
        ReDim aShortestDistances(totalVertices - 1)
        ReDim aPreviousVertices(totalVertices - 1)
        For i As Integer = 0 To totalVertices - 1
            unvisitedVertices.Add(i)
            aShortestDistances(i) = Double.PositiveInfinity
        Next

        aShortestDistances(0) = 0

        'Generate information about shortest distances
        While unvisitedVertices.Count > 0
            Dim u As Integer = getClosestUnvisitedVertex()
            For i As Integer = 0 To totalVertices - 1
                If adjacencyMatrix(u, i) > 0 Then
                    If aShortestDistances(i) > aShortestDistances(u) + adjacencyMatrix(u, i) Then
                        aShortestDistances(i) = aShortestDistances(u) + adjacencyMatrix(u, i)
                        aPreviousVertices(i) = u
                    End If
                End If
            Next
        End While
    End Sub
    Private Function getClosestUnvisitedVertex() As Integer
        Dim min = Double.PositiveInfinity
        Dim vertex As Integer = -1

        For Each val As Integer In unvisitedVertices
            If aShortestDistances(val) <= min Then
                min = aShortestDistances(val)
                vertex = val
            End If
        Next
        unvisitedVertices.Remove(vertex)
        Return vertex
    End Function

    'return the shortest distances array
    Public ReadOnly Property dist() As Double()
        Get
            Return aShortestDistances
        End Get
    End Property

End Class

The class constructor is passed the adjacency matrix of a graph and the total number of vertices.

The line of code…

aShortestDistances(0) = 0

…specifies the distance of the starting vertex from the starting vertex! That is, it specifies that the distance to vertex 0 from vertex 0 is 0. This can be changed to specify a different starting vertex. For example, changing this line to…

aShortestDistances(3) = 0

…would redefine the starting vertex as vertex 3. An additional parameter could be added to the constructor to specify this information.

The constructor generates the path information as soon as the Dijkstra class is instantiated. The path information is put into an array called aShortestDistances which can be accessed via a read only property of the class called dist.

The Dijkstra class makes use of a helper method called getClosestUnvisitedVertex.  This method does exactly what its name suggests.

The following code, which is run from a button on a form, creates an instance of the Dijkstra class by the name of ‘distances’. Needless to say, the graph has already been created so the adjacency matrix is already populated. The dist method of the distances object contains the path information which is used to populated a list box on the form.

    Private Sub btnShortestPaths_Click(sender As Object, e As EventArgs) Handles btnShortestPaths.Click
        Dim distances As New Dijkstra(g.GetAdjacencyMatrix, 5)
        Dim item = distances.dist

        For i As Integer = 0 To item.Length - 1
            ListBox1.Items.Add("Node " & i & " Path Distance = " & item(i))
        Next
    End Sub