Bellman Ford Algorithm ( Simple Implementation ) | Python3 program for Bellman - Ford 's single source shortest path algorithm. ; The main function that finds shortest distances from src to all other vertices using Bellman - Ford algorithm . The function also detects negative weight cycle The row graph [ i ] represents i - th edge with three values u , v and w . ; Initialize distance of all vertices as infinite . ; initialize distance of source as 0 ; Relax all edges | V | - 1 times . A simple shortest path from src to any other vertex can have at - most | V | - 1 edges ; check for negative - weight cycles . The above step guarantees shortest distances if graph doesn 't contain  negative weight cycle. If we get a  shorter path, then there is a cycle. ; Driver Code ; Every edge has three values ( u , v , w ) where the edge is from vertex u to v . And weight of the edge is w .
from sys import maxsize NEW_LINE def BellmanFord ( graph , V , E , src ) : NEW_LINE INDENT dis = [ maxsize ] * V NEW_LINE dis [ src ] = 0 NEW_LINE for i in range ( V - 1 ) : NEW_LINE INDENT for j in range ( E ) : NEW_LINE INDENT if dis [ graph [ j ] [ 0 ] ] + graph [ j ] [ 2 ] < dis [ graph [ j ] [ 1 ] ] : NEW_LINE INDENT dis [ graph [ j ] [ 1 ] ] = dis [ graph [ j ] [ 0 ] ] + graph [ j ] [ 2 ] NEW_LINE DEDENT DEDENT DEDENT for i in range ( E ) : NEW_LINE INDENT x = graph [ i ] [ 0 ] NEW_LINE y = graph [ i ] [ 1 ] NEW_LINE weight = graph [ i ] [ 2 ] NEW_LINE if dis [ x ] != maxsize and dis [ x ] + weight < dis [ y ] : NEW_LINE INDENT print ( " Graph ▁ contains ▁ negative ▁ weight ▁ cycle " ) NEW_LINE DEDENT DEDENT print ( " Vertex ▁ Distance ▁ from ▁ Source " ) NEW_LINE for i in range ( V ) : NEW_LINE INDENT print ( " % d TABSYMBOL TABSYMBOL % d " % ( i , dis [ i ] ) ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT graph = [ [ 0 , 1 , - 1 ] , [ 0 , 2 , 4 ] , [ 1 , 2 , 3 ] , [ 1 , 3 , 2 ] , [ 1 , 4 , 2 ] , [ 3 , 2 , 5 ] , [ 3 , 1 , 1 ] , [ 4 , 3 , - 3 ] ] NEW_LINE BellmanFord ( graph , V , E , 0 ) NEW_LINE DEDENT