Multistage Graph ( Shortest Path ) | CPP program to find shortest distance in a multistage graph . ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  8 NEW_LINE #define INF  INT_MAX NEW_LINE int shortestDist ( int graph [ N ] [ N ] ) { int dist [ N ] ; dist [ N - 1 ] = 0 ; for ( int i = N - 2 ; i >= 0 ; i -- ) { dist [ i ] = INF ; for ( int j = i ; j < N ; j ++ ) { if ( graph [ i ] [ j ] == INF ) continue ; dist [ i ] = min ( dist [ i ] , graph [ i ] [ j ] + dist [ j ] ) ; } } return dist [ 0 ] ; } int main ( ) { int graph [ N ] [ N ] = { { 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 } , { INF , INF , INF , INF , INF , INF , INF , INF } } ; cout << shortestDist ( graph ) ; return 0 ; }