Shortest Path with even number of Edges from Source to Destination | C ++ program for the above approach ; Adjacency List : to represent graph ; Distance Array : to store shortest distance to every node ; returns value which will represent even_x ; returns value which will represent odd_x ; converting edge ( a -> b ) to 2 different edges i . e . ( a -> b ) converts to ( 1 ) . even_a -> odd_b ( 2 ) . odd_a -> even_b since , graph is undirected , so we push them in reverse order too hence , 4 push_back operations are there . ; Function calculates shortest distance to all nodes from " source " using Dijkstra Shortest Path Algorithm and returns shortest distance to " destination " ; Priority Queue / min - heap to store and process ( distance , node ) ; pushing source node to priority queue and dist from source to source is set to 0 ; U is the node at top of the priority queue note that pq . top ( ) . first refers to the Distance and pq . top ( ) . second will refer to the Node ; exploring all neighbours of node u ; v is neighbour node of u and c is the cost / weight of edge ( u , v ) ; relaxation : checking if there is a shorter path to v via u ; updating distance of v ; returning shortest distance to " destination " ; Driver function ; n = number of Nodes , m = number of Edges ; if ans is INF : There is no even length path from source to destination else path exists and we print the shortest distance
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAXX = 10000 , INF = 1e9 ; vector < vector < pair < int , int > > > adj ( MAXX * 10 + 3 ) ; vector < int > dist ( MAXX * 10 + 3 , INF ) ; int even ( int x ) { return x * 10 + 2 ; } int odd ( int x ) { return x * 10 + 1 ; } void addEdge ( int a , int b , int cost ) { adj [ even ( a ) ] . push_back ( { odd ( b ) , cost } ) ; adj [ odd ( a ) ] . push_back ( { even ( b ) , cost } ) ; adj [ odd ( b ) ] . push_back ( { even ( a ) , cost } ) ; adj [ even ( b ) ] . push_back ( { odd ( a ) , cost } ) ; } int dijkstra ( int source , int destination ) { priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > pq ; pq . push ( { 0 , even ( source ) } ) ; dist [ even ( source ) ] = 0 ; while ( ! pq . empty ( ) ) { int u = pq . top ( ) . second ; pq . pop ( ) ; for ( pair < int , int > p : adj [ u ] ) { int v = p . first ; int c = p . second ; if ( dist [ u ] + c < dist [ v ] ) { dist [ v ] = dist [ u ] + c ; pq . push ( { dist [ v ] , v } ) ; } } } return dist [ even ( destination ) ] ; } int main ( ) { int n = 5 , m = 6 ; addEdge ( 1 , 2 , 1 ) ; addEdge ( 2 , 3 , 2 ) ; addEdge ( 2 , 5 , 15 ) ; addEdge ( 3 , 5 , 1 ) ; addEdge ( 3 , 4 , 4 ) ; addEdge ( 5 , 4 , 3 ) ; int source = 1 ; int destination = n ; int ans = dijkstra ( source , destination ) ; if ( ans == INF ) cout << " - 1" << " STRNEWLINE " ; else cout << ans << " STRNEWLINE " ; return 0 ; }