Dijkstra's Algorithm

Dijkstra's algorithm, also known as single-source shortest paths, solves the problem of finding the shortest path from a point in a graph (the source) to a destination. It is a greedy algorithm and similar to Prim's algorithm. Algorithm starts at the source vertex, s, it grows a tree, T, that ultimately spans all vertices reachable from S. Vertices are added to T in order of distance i.e., first S, then the vertex closest to S, then the next closest, and so on.

									Private Shared Function MinimumDistance(distance As Integer(), shortestPathTreeSet As Boolean(), verticesCount As Integer) As Integer
	Dim min As Integer = Integer.MaxValue
	Dim minIndex As Integer = 0

	For v As Integer = 0 To verticesCount - 1
		If shortestPathTreeSet(v) = False AndAlso distance(v) <= min Then
			min = distance(v)
			minIndex = v
		End If
	Next

	Return minIndex
End Function

Private Shared Sub Print(distance As Integer(), verticesCount As Integer)
	Console.WriteLine("Vertex    Distance from source")

	For i As Integer = 0 To verticesCount - 1
		Console.WriteLine("{0}" & vbTab & "  {1}", i, distance(i))
	Next
End Sub

Public Shared Sub Dijkstra(graph As Integer(,), source As Integer, verticesCount As Integer)
	Dim distance As Integer() = New Integer(verticesCount - 1) {}
	Dim shortestPathTreeSet As Boolean() = New Boolean(verticesCount - 1) {}

	For i As Integer = 0 To verticesCount - 1
		distance(i) = Integer.MaxValue
		shortestPathTreeSet(i) = False
	Next

	distance(source) = 0

	For count As Integer = 0 To verticesCount - 2
		Dim u As Integer = MinimumDistance(distance, shortestPathTreeSet, verticesCount)
		shortestPathTreeSet(u) = True

		For v As Integer = 0 To verticesCount - 1
			If Not shortestPathTreeSet(v) AndAlso Convert.ToBoolean(graph(u, v)) AndAlso distance(u) <> Integer.MaxValue AndAlso distance(u) + graph(u, v) < distance(v) Then
				distance(v) = distance(u) + graph(u, v)
			End If
		Next
	Next

	Print(distance, verticesCount)
End Sub

Example

									Dim graph As Integer(,) = {
	{0, 4, 0, 0, 0, 0, 0, 8, 0},
	{4, 0, 8, 0, 0, 0, 0, 11, 0},
	{0, 8, 0, 7, 0, 4, 0, 0, 2},
	{0, 0, 7, 0, 9, 14, 0, 0, 0},
	{0, 0, 0, 9, 0, 10, 0, 0, 0},
	{0, 0, 4, 0, 10, 0, 2, 0, 0},
	{0, 0, 0, 14, 0, 2, 0, 1, 6},
	{8, 11, 0, 0, 0, 0, 1, 0, 7},
	{0, 0, 2, 0, 0, 0, 6, 7, 0}
}

Dijkstra(graph, 0, 9)

Output

									Vertex    Distance from source
0         0
1         4
2         12
3         19
4         21
5         11
6         9
7         8
8         14