Multistage Graph ( Shortest Path ) | Returns shortest distance from 0 to N - 1. ; dist [ i ] is going to store shortest distance from node i to node N - 1. ; Calculating shortest path for rest of the nodes ; Initialize distance from i to destination ( N - 1 ) ; Check all nodes of next stages to find shortest distance from i to N - 1. ; Reject if no edge exists ; We apply recursive equation to distance to target through j . and compare with minimum distance so far . ; Driver code ; Graph stored in the form of an adjacency Matrix
def shortestDist ( graph ) : NEW_LINE INDENT global INF NEW_LINE dist = [ 0 ] * N NEW_LINE dist [ N - 1 ] = 0 NEW_LINE for i in range ( N - 2 , - 1 , - 1 ) : NEW_LINE INDENT dist [ i ] = INF NEW_LINE for j in range ( N ) : NEW_LINE INDENT if graph [ i ] [ j ] == INF : NEW_LINE INDENT continue NEW_LINE DEDENT dist [ i ] = min ( dist [ i ] , graph [ i ] [ j ] + dist [ j ] ) NEW_LINE DEDENT DEDENT return dist [ 0 ] NEW_LINE DEDENT N = 8 NEW_LINE INF = 999999999999 NEW_LINE graph = [ [ INF , 1 , 2 , 5 , INF , INF , INF , INF ] , [ INF , INF , INF , INF , 4 , 11 , INF , INF ] , [ INF , INF , INF , INF , 9 , 5 , 16 , INF ] , [ INF , INF , INF , INF , INF , INF , 2 , INF ] , [ INF , INF , INF , INF , INF , INF , INF , 18 ] , [ INF , INF , INF , INF , INF , INF , INF , 13 ] , [ INF , INF , INF , INF , INF , INF , INF , 2 ] ] NEW_LINE print ( shortestDist ( graph ) ) NEW_LINE