Shortest Path with even number of Edges from Source to Destination

0 0 10 minutes read

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 graph
vector<vector<pair<int, int> > >
    adj(MAXX * 10 + 3);
 
// Distance Array: to store shortest
// distance to every node
vector<int> dist(MAXX * 10 + 3, INF);
 
// returns value which will
// represent even_x
int even(int x)
{
    return x * 10 + 2;
}
// returns value which will
// represent odd_x
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.
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 function
int 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 node
static int[] dist = new int[MAXX * 10 + 3];
 
// 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;
}
 
// 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 code
public 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 approach
import heapq as hq
 
MAXX = 10000
INF = 1e9
 
# Adjacency List: to represent graph
adj = [[] for _ in range(MAXX * 10 + 3)]
 
# Distance Array: to store shortest
# distance to every node
dist = [INF] * (MAXX * 10 + 3)
 
# returns value which will
# represent even_x
def even(x):
    return x * 10 + 2
 
 
# returns value which will
# represent odd_x
def 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 function
if __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 graph
const adj = new Array(MAXX * 10 + 3).fill(null).map(() => []);
 
// Distance Array: to store shortest
// distance to every node
const dist = new Array(MAXX * 10 + 3).fill(INF);
 
// returns value which will
// represent even_x
function even(x) {
  return x * 10 + 2;
}
 
// returns value which will
// represent odd_x
function 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:

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 zambiatek!