Bellman Ford Algorithm:

Bellman Ford is used in case of negative weights as Dijkstra's cannot handle negative weights

Time Complexity is O(VE)

Algorithm:

• Make a dictionary where you store the initial distances of all vertices. Except for the source vertex, rest all the vertices will have value of INFINITY
• Pick a vertex and check if its initial distance value is not infinity after which calculate its cost for its neighbours.
• Check whether they are less then infinity if yes then replace the value in distance dictionary.
• Repeat Step 2 and 3 for No. if vertices-1 times.
• The final distance dictionary will give you the minimum distance from source to all the nodes

Explanation: https://www.youtube.com/watch?v=obWXjtg0L64

graph = {
    0:[(1,10),(5,8)],
    1:[(3,2)],
    2:[(1,1)],
    3:[(2,-2)],
    4:[(1,-4),(3,-1)],
    5:[(4,1)]

    }


def bellman_ford(graph,start):
    dist = {}
    for i in range(1,6):
        dist[i] = float('inf')

    dist[start] = 0

    for i in range(5):
        for z in range(len(graph)):
            for nbr,cost in graph[z]:
                if dist[z]!=float('inf') and dist[z]+cost<dist[nbr]:
                    dist[nbr] = dist[z]+cost

    print dist


bellman_ford(graph,0)