Given an undirected graph G, the task is to find the shortest path of even-length, given 1 as Source Node and N as Destination Node. Path length refers to the number of edges present in a path (not the cost of the path).
Examples:
Input: N = 5, G is given below:
Output: 10
Explanation:
All paths from 1(source node) to 5 (destination node) are:
1->2->5
Cost: 16 Length: 2(even)
1->2->3->5
Cost: 4 Length: 3(odd)
1->2->3->4->5
Cost: 10 Length: 4(even)
The shortest path is 1->2->3->5 with total cost 4, but it has an odd-length path and since we are interested in even-length paths only, the shortest path with even-length is 1->2->3->4->5, with total cost 10.Input 2: N = 4, G is given below:
Output: -1
Explanation:
There is no path of even-length from 1(source node) to 4(destination node).
Approach:
Create a new Graph (G’). For each node V in initial graph G, create two new nodes V_even and V_odd.
Here, V_odd will be represented as ((V * 10) + 1) and V_even as ((V * 10) + 2).
For example, if node V = 4 then V_odd = 41 and V_even = 42.
Now, for each edge (U, V) in G, add two new edges in G’, (U_even, V_odd) and (U_odd, V_even). Finally, find the Shortest path from (source_even) node to (destination_even) node using Dijkstra Shortest Path Algorithm.
For Graph given in Input 1(above), G’ can be represented as:
It can observed from the graph G’ that there are only even length paths from (1_even) to (5_even). Thus, the odd-length paths get separated in G’ and the required shortest path can be obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const int MAXX = 10000, INF = 1e9;// Adjacency List: to represent graphvector<vector<pair<int, int> > > adj(MAXX * 10 + 3);// Distance Array: to store shortest// distance to every nodevector<int> dist(MAXX * 10 + 3, INF);// returns value which will// represent even_xint even(int x){ return x * 10 + 2;}// returns value which will// represent odd_xint odd(int x){ return x * 10 + 1;}// 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.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 });}// Function calculates shortest// distance to all nodes from// "source" using Dijkstra// Shortest Path Algorithm// and returns shortest distance// to "destination"int dijkstra(int source, int destination){ /* Priority Queue/min-heap to store and process (distance, node) */ priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; // pushing source node to // priority queue and dist from // source to source is set to 0 pq.push({ 0, even(source) }); dist[even(source)] = 0; while (!pq.empty()) { // 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 int u = pq.top().second; pq.pop(); // exploring all neighbours // of node u for (pair<int, int> p : adj[u]) { /* v is neighbour node of u and c is the cost/weight of edge (u, v) */ int v = p.first; int c = p.second; // relaxation: checking if there // is a shorter path to v via u if (dist[u] + c < dist[v]) { // updating distance of v dist[v] = dist[u] + c; pq.push({ dist[v], v }); } } } // returning shortest // distance to "destination" return dist[even(destination)];}// Driver functionint main(){ // n = number of Nodes, // m = number of Edges 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 is INF: There is no // even length path from source // to destination else path // exists and we print the // shortest distance if (ans == INF) cout << "-1" << "\n"; else cout << ans << "\n"; return 0;} |
Java
// Java program for the above approach import java.util.ArrayList;import java.util.Arrays;import java.util.PriorityQueue;class GFG{static class Pair implements Comparable<Pair> { int first, second; public Pair(int first, int second) { this.first = first; this.second = second; } @Override public int compareTo(GFG.Pair o) { if (this.first == o.first) { return this.second - o.second; } return this.first - o.first; }}static final int MAXX = 10000, INF = (int)1e9;// Adjacency List: to represent graph@SuppressWarnings("unchecked")static ArrayList<Pair>[] adj = new ArrayList[MAXX * 10 + 3];// Distance Array: to store shortest// distance to every nodestatic int[] dist = new int[MAXX * 10 + 3];// Returns value which will// represent even_xstatic int even(int x) { return x * 10 + 2;}// Returns value which will// represent odd_xstatic int odd(int x){ return x * 10 + 1;}// 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.static void addEdge(int a, int b, int cost){ adj[even(a)].add(new Pair(odd(b), cost)); adj[odd(a)].add(new Pair(even(b), cost)); adj[odd(b)].add(new Pair(even(a), cost)); adj[even(b)].add(new Pair(odd(a), cost));}// Function calculates shortest// distance to all nodes from// "source" using Dijkstra// Shortest Path Algorithm// and returns shortest distance// to "destination"static int dijkstra(int source, int destination){ // Priority Queue/min-heap to store // and process (distance, node) PriorityQueue<Pair> pq = new PriorityQueue<>(); // Pushing source node to // priority queue and dist from // source to source is set to 0 pq.add(new Pair(0, even(source))); dist[even(source)] = 0; while (!pq.isEmpty()) { // 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 int u = pq.poll().second; // Exploring all neighbours // of node u for(Pair p : adj[u]) { // v is neighbour node of u and // c is the cost/weight of edge (u, v) int v = p.first; int c = p.second; // Relaxation: checking if there // is a shorter path to v via u if (dist[u] + c < dist[v]) { // Updating distance of v dist[v] = dist[u] + c; pq.add(new Pair(dist[v], v)); } } } // Returning shortest // distance to "destination" return dist[even(destination)];}// Driver codepublic static void main(String[] args){ for(int i = 0; i < MAXX * 10 + 3; i++) { adj[i] = new ArrayList<Pair>(); } Arrays.fill(dist, INF); // n = number of Nodes, // m = number of Edges 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 is INF: There is no // even length path from source // to destination else path // exists and we print the // shortest distance if (ans == INF) System.out.println("-1"); else System.out.println(ans);}}// This code is contributed by sanjeev2552 |
Python3
# Python3 program for the above approachimport heapq as hqMAXX = 10000INF = 1e9# Adjacency List: to represent graphadj = [[] for _ in range(MAXX * 10 + 3)]# Distance Array: to store shortest# distance to every nodedist = [INF] * (MAXX * 10 + 3)# returns value which will# represent even_xdef even(x): return x * 10 + 2# returns value which will# represent odd_xdef odd(x): return x * 10 + 1# 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 append operations are# there.def addEdge(a, b, cost): adj[even(a)].append((odd(b), cost)) adj[odd(a)].append((even(b), cost)) adj[odd(b)].append((even(a), cost)) adj[even(b)].append((odd(a), cost))# Function calculates shortest# distance to all nodes from# "source" using Dijkstra# Shortest Path Algorithm# and returns shortest distance# to "destination"def dijkstra(source, destination): # Priority Queue/min-heap # to store and process # (distance, node) pq = [] # pushing source node to # priority queue and dist from # source to source is set to 0 hq.heappush(pq, (0, even(source))) dist[even(source)] = 0 while pq: # U is the node at top # of the priority queue # note that pq.top()[1] # refers to the Distance # and pq.top()[1] # will refer to the Node u = hq.heappop(pq)[1] # exploring all neighbours # of node u # v is neighbour node of u # and c is the cost/weight # of edge (u, v) for v, c in adj[u]: # relaxation: checking if there # is a shorter path to v via u if dist[u] + c < dist[v]: # updating distance of v dist[v] = dist[u] + c hq.heappush(pq, (dist[v], v)) # returning shortest # distance to "destination" return dist[even(destination)]# Driver functionif __name__ == "__main__": # n = number of Nodes, # m = number of Edges 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) source = 1 destination = n ans = dijkstra(source, destination) # if ans is INF: There is no # even length path from source # to destination else path # exists and we print # shortest distance if ans == INF: print(-1) else: print(ans) |
C#
using System;using System.Collections.Generic;class GFG{ // 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. static void addEdge(int a, int b, int cost, List<List<Tuple<int, int>>> adj) { int evenA = even(a); int oddB = odd(b); int oddA = odd(a); int evenB = even(b); adj[evenA].Add(Tuple.Create(oddB, cost)); adj[oddA].Add(Tuple.Create(evenB, cost)); adj[oddB].Add(Tuple.Create(evenA, cost)); adj[evenB].Add(Tuple.Create(oddA, cost)); } // returns value which will represent even_x static int even(int x) { return x * 10 + 2; } // returns value which will represent odd_x static int odd(int x) { return x * 10 + 1; } static int Dijkstra(int source, int destination, List<List<Tuple<int, int>>> adj, List<int> dist) { // Priority Queue/min-heap to store and process (distance, node) var pq = new SortedSet<Tuple<int, int>>(Comparer<Tuple<int, int>>.Create((a, b) => a.Item1.CompareTo(b.Item1))); pq.Add(Tuple.Create(0, even(source))); dist[even(source)] = 0; while (pq.Count > 0) { // U is the node at top of the priority queue // note that pq.Keys[0].Item1 refers to the Distance // and pq.Values[0] will refer to the Node var u = pq.Min; pq.Remove(u); // exploring all neighbours of node u foreach (var p in adj[u.Item2]) { int v = p.Item1; int c = p.Item2;// 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 if (dist[u.Item2] + c < dist[v]) { dist[v] = dist[u.Item2] + c; pq.Add(Tuple.Create(dist[v], v)); } } } // returning shortest distance to "destination" return dist[even(destination)]; } //Driver code static void Main(string[] args) {// n = number of Nodes, m = number of Edges int n = 5, m = 6; var adj = new List<List<Tuple<int, int>>>(); var dist = new List<int>(); for (int i = 0; i < n * 10 + 3; i++) { adj.Add(new List<Tuple<int, int>>()); dist.Add(int.MaxValue); } addEdge(1, 2, 1, adj); addEdge(2, 3, 2, adj); addEdge(2, 5, 15, adj); addEdge(3, 5, 1, adj); addEdge(3, 4, 4, adj); addEdge(5, 4, 3, adj); int source = 1; int destination = n; int ans = Dijkstra(source, destination, adj, dist); if (ans == int.MaxValue) { Console.WriteLine("-1"); } else { Console.WriteLine(ans); } }} |
Javascript
class PriorityQueue { constructor() { this.items = []; } enqueue(item, priority) { this.items.push({ item, priority }); this.items.sort((a, b) => a.priority - b.priority); } dequeue() { if (this.isEmpty()) { return null; } return this.items.shift().item; } isEmpty() { return this.items.length === 0; }}const MAXX = 10000;const INF = 1e9;// Adjacency List: to represent graphconst adj = new Array(MAXX * 10 + 3).fill(null).map(() => []);// Distance Array: to store shortest// distance to every nodeconst dist = new Array(MAXX * 10 + 3).fill(INF);// returns value which will// represent even_xfunction even(x) { return x * 10 + 2;}// returns value which will// represent odd_xfunction odd(x) { return x * 10 + 1;}// 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 addEdge(a, b, cost) { adj[even(a)].push([odd(b), cost]); adj[odd(a)].push([even(b), cost]); adj[odd(b)].push([even(a), cost]); adj[even(b)].push([odd(a), cost]);}// Function calculates shortest// distance to all nodes from// "source" using Dijkstra// Shortest Path Algorithm// and returns shortest distance// to "destination"function dijkstra(source, destination) { /* Priority Queue/min-heap to store and process (distance, node) */ const pq = new PriorityQueue(); // pushing source node to // priority queue and dist from // source to source is set to 0 pq.enqueue(even(source), 0); dist[even(source)] = 0; while (!pq.isEmpty()) { // U is the node at top // of the priority queue // note that pq.top().priority // refers to the Distance // and pq.top().item // will refer to the Node const u = pq.dequeue(); // exploring all neighbours // of node u for (const [v, c] of adj[u]) { // relaxation: checking if there // is a shorter path to v via u if (dist[u] + c < dist[v]) { // updating distance of v dist[v] = dist[u] + c; pq.enqueue(v, dist[v]); } } } // returning shortest // distance to "destination" return dist[even(destination)];}// Driver function // n = number of Nodes, // m = number of Edges const 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); const source = 1; const destination = n; const ans = dijkstra(source, destination); // if ans is INF: There is no // even length path from source // to destination else path // exists and we print the // shortest distance if (ans == Infinity) console.log(-1) else console.log(ans) |
Output:
10
Time Complexity: (E * log(V))
Auxiliary Space: O(V + E)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
