# 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
```