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