human
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"
How can the above be solved in Python?
assistant
#Here is code to multistage Graph ( Shortest Path ) and the other steps required.
 def shortestDist ( graph ) :
	global INF
	dist = [ 0 ] * N
	dist [ N - 1 ] = 0
	for i in range ( N - 2 , - 1 , - 1 ) :
		dist [ i ] = INF
		for j in range ( N ) :
			if graph [ i ] [ j ] == INF :
				continue
			dist [ i ] = min ( dist [ i ] , graph [ i ] [ j ] + dist [ j ] )
	return dist [ 0 ]
N = 8
INF = 999999999999
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 ] ]
print ( shortestDist ( graph ) )