Bellman Ford Algorithm in Python

Bellman-Ford Algorithm

Bellman Ford Algorithm is an algorithm to find Single Source Shortest Paths similar to the except the fact that it allows the use of negative edge weights but not a negative cycle .

Algorithm

• Initialise a dictionary $D$ that stores the distance and $D(v) = \begin{bmatrix}0 \text{, If v is source vertex}\\ \infin \text{, otherwise}\end{bmatrix}$
• Pick a vertex $j$ that has an edge $(j,k)$ and set $D(k) = min(D(k), D(j)+\text{weight}(j, k))$
• Repeat the step $2$ for $n-1$ times.

Implementation

Using Numpy Array

def BellmanFord(adj, source):
    rows, cols, x = adj.shape
    distance = {k: float('inf') for k in range(rows)}

    distance[source] = 0

    for i in range(rows):
        for u in range(rows):
            for j in range(cols):
                if adj[i, j, 0] == 1:
                    distance[j] = min(distance[j], distance[i] + adj[i, j, 1])

    return distance

Using Adjancency List

def BellmanFord(adj, source):
    vertices = len(adj.keys())

    distance = {k: float('inf') for k in range(vertices)}
    distance[source] = 0

    for i in adj:
        for u in adj:
            for vertex, dist in adj[u]:
                distance[vertex] = min(distance[vertex], distance[u] + dist)

    return distance

Time Complexity

Using the numpy method the time complexity is $O(n^3)$.Shifting to the Adjacency List the time complexity becomes $O(mn)$ where $m$ is the number of edges and $n$ is the number of vertices.