Bellman–Ford Algorithm

Bellman–Ford algorithm, also known as Bellman–Ford–Moore algorithm, is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.

									Public Structure Edge
	Public Source As Integer
	Public Destination As Integer
	Public Weight As Integer
End Structure

Public Structure Graph
	Public VerticesCount As Integer
	Public EdgesCount As Integer
	Public edge As Edge()
End Structure

Public Shared Function CreateGraph(verticesCount As Integer, edgesCount As Integer) As Graph
	Dim graph As New Graph()
	graph.VerticesCount = verticesCount
	graph.EdgesCount = edgesCount
	graph.edge = New Edge(graph.EdgesCount - 1) {}

	Return graph
End Function

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

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

Public Shared Sub BellmanFord(graph As Graph, source As Integer)
	Dim verticesCount As Integer = graph.VerticesCount
	Dim edgesCount As Integer = graph.EdgesCount
	Dim distance As Integer() = New Integer(verticesCount - 1) {}

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

	distance(source) = 0

	For i As Integer = 1 To verticesCount - 1
		For j As Integer = 0 To edgesCount - 1
			Dim u As Integer = graph.edge(j).Source
			Dim v As Integer = graph.edge(j).Destination
			Dim weight As Integer = graph.edge(j).Weight

			If distance(u) <> Integer.MaxValue AndAlso distance(u) + weight < distance(v) Then
				distance(v) = distance(u) + weight
			End If
		Next
	Next

	For i As Integer = 0 To edgesCount - 1
		Dim u As Integer = graph.edge(i).Source
		Dim v As Integer = graph.edge(i).Destination
		Dim weight As Integer = graph.edge(i).Weight

		If distance(u) <> Integer.MaxValue AndAlso distance(u) + weight < distance(v) Then
			Console.WriteLine("Graph contains negative weight cycle.")
		End If
	Next

	Print(distance, verticesCount)
End Sub

Example

									Dim verticesCount As Integer = 5
Dim edgesCount As Integer = 8
Dim graph As Graph = CreateGraph(verticesCount, edgesCount)

' Edge 0-1
graph.edge(0).Source = 0
graph.edge(0).Destination = 1
graph.edge(0).Weight = -1

' Edge 0-2
graph.edge(1).Source = 0
graph.edge(1).Destination = 2
graph.edge(1).Weight = 4

' Edge 1-2
graph.edge(2).Source = 1
graph.edge(2).Destination = 2
graph.edge(2).Weight = 3

' Edge 1-3
graph.edge(3).Source = 1
graph.edge(3).Destination = 3
graph.edge(3).Weight = 2

' Edge 1-4
graph.edge(4).Source = 1
graph.edge(4).Destination = 4
graph.edge(4).Weight = 2

' Edge 3-2
graph.edge(5).Source = 3
graph.edge(5).Destination = 2
graph.edge(5).Weight = 5

' Edge 3-1
graph.edge(6).Source = 3
graph.edge(6).Destination = 1
graph.edge(6).Weight = 1

' Edge 4-3
graph.edge(7).Source = 4
graph.edge(7).Destination = 3
graph.edge(7).Weight = -3

BellmanFord(graph, 0)

Output

									Vertex   Distance from source
0        0
1        -1
2        2
3        -2
4        1