Given a directed graph with N nodes and E edges, a source S and a destination D nodes. The task is to find the path with the minimum XOR sum of edges from S to D. If there is no path from S to D then print -1.
Examples:
Input: N = 3, E = 3, Edges = {{{1, 2}, 5}, {{1, 3}, 9}, {{2, 3}, 1}}, S = 1, and D = 3
Output: 4
The path with smallest XOR of edges weight will be 1->2->3
with XOR sum as 5^1 = 4.Input: N = 3, E = 3, Edges = {{{3, 2}, 5}, {{3, 3}, 9}, {{3, 3}, 1}}, S = 1, and D = 3
Output: -1
Approach: The idea is to use Dijkstra’s shortest path algorithm with a slight variation. Below is the step-wise approach for the problem:
- Base Case: If the source node is equal to the destination then return 0.
- Initialise a priority-queue with source node and its weight as 0 and a visited array.
- While priority queue is not empty:
- Pop the top-most element from priority queue. Let’s call it as current node.
- Check if the current node is already visited with the help of the visited array, If yes then continue.
- If the current node is the destination node then return the XOR sum distance of the current node from the source node.
- Iterate all the nodes adjacent to current node and push into priority queue and their distance as XOR sum with the current distance and edge weight.
- Otherwise, there is no path from source to destination. Therefore, return -1
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the smallest// xor sum of edgesdouble minXorSumOfEdges( int s, int d, vector<vector<pair<int, int> > > gr){ // If the source is equal // to the destination if (s == d) return 0; // Initialise the priority queue set<pair<int, int> > pq; pq.insert({ 0, s }); // Visited array bool v[gr.size()] = { 0 }; // While the priority-queue // is not empty while (pq.size()) { // Current node int curr = pq.begin()->second; // Current xor sum of distance int dist = pq.begin()->first; // Popping the top-most element pq.erase(pq.begin()); // If already visited continue if (v[curr]) continue; // Marking the node as visited v[curr] = 1; // If it is a destination node if (curr == d) return dist; // Traversing the current node for (auto it : gr[curr]) pq.insert({ dist ^ it.second, it.first }); } // If no path exists return -1;}// Driver codeint main(){ int n = 3; // Graph as adjacency matrix vector<vector<pair<int, int> > > gr(n + 1); // Input edges gr[1].push_back({ 3, 9 }); gr[2].push_back({ 3, 1 }); gr[1].push_back({ 2, 5 }); // Source and destination int s = 1, d = 3; cout << minXorSumOfEdges(s, d, gr); return 0;} |
Java
// Java implementation of the approachimport java.util.PriorityQueue;import java.util.ArrayList;class Pair implements Comparable<Pair> { int first, second; public Pair(int first, int second) { this.first = first; this.second = second; } @Override public int compareTo(Pair p) { if (this.first == p.first) { return this.second - p.second; } return this.first - p.first; }}class GFG{// Function to return the smallest// xor sum of edgesstatic int minXorSumOfEdges(int s, int d, ArrayList<ArrayList<Pair>> gr) { // If the source is equal // to the destination if (s == d) return 0; // Initialise the priority queue PriorityQueue<Pair> pq = new PriorityQueue<>(); pq.add(new Pair(0, s)); // Visited array boolean[] v = new boolean[gr.size()]; // While the priority-queue // is not empty while (!pq.isEmpty()) { // Iterator<Pair> itr = pq.iterator(); // Current node Pair p = pq.poll(); int curr = p.second; // Current xor sum of distance int dist = p.first; // If already visited continue if (v[curr]) continue; // Marking the node as visited v[curr] = true; // If it is a destination node if (curr == d) return dist; // Traversing the current node for(Pair it : gr.get(curr)) pq.add(new Pair(dist ^ it.second, it.first)); } // If no path exists return -1;}// Driver codepublic static void main(String[] args) { int n = 3; // Graph as adjacency matrix ArrayList<ArrayList<Pair>> gr = new ArrayList<>(); for(int i = 0; i < n + 1; i++) { gr.add(new ArrayList<Pair>()); } // Input edges gr.get(1).add(new Pair(3, 9)); gr.get(2).add(new Pair(3, 1)); gr.get(1).add(new Pair(2, 5)); // Source and destination int s = 1, d = 3; System.out.println(minXorSumOfEdges(s, d, gr));}}// This code is contributed by sanjeev2552 |
Python3
# Python3 implementation of the approachfrom collections import deque# Function to return the smallest# xor sum of edgesdef minXorSumOfEdges(s, d, gr): # If the source is equal # to the destination if (s == d): return 0 # Initialise the priority queue pq = [] pq.append((0, s)) # Visited array v = [0] * len(gr) # While the priority-queue # is not empty while (len(pq) > 0): pq = sorted(pq) # Current node curr = pq[0][1] # Current xor sum of distance dist = pq[0][0] # Popping the top-most element del pq[0] # If already visited continue if (v[curr]): continue # Marking the node as visited v[curr] = 1 # If it is a destination node if (curr == d): return dist # Traversing the current node for it in gr[curr]: pq.append((dist ^ it[1], it[0])) # If no path exists return -1# Driver codeif __name__ == '__main__': n = 3 # Graph as adjacency matrix gr = [[] for i in range(n + 1)] # Input edges gr[1].append([ 3, 9 ]) gr[2].append([ 3, 1 ]) gr[1].append([ 2, 5 ]) # Source and destination s = 1 d = 3 print(minXorSumOfEdges(s, d, gr)) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG { // Function to return the smallest // xor sum of edges static int minXorSumOfEdges(int s, int d, List<List<Tuple<int,int>>> gr) { // If the source is equal // to the destination if (s == d) return 0; // Initialise the priority queue List<Tuple<int,int>> pq = new List<Tuple<int,int>>(); pq.Add(new Tuple<int,int>(0, s)); // Visited array int[] v = new int[gr.Count]; // While the priority-queue // is not empty while (pq.Count > 0) { pq.Sort(); // Current node int curr = pq[0].Item2; // Current xor sum of distance int dist = pq[0].Item1; // Popping the top-most element pq.RemoveAt(0); // If already visited continue if(v[curr] != 0) continue; // Marking the node as visited v[curr] = 1; // If it is a destination node if (curr == d) return dist; // Traversing the current node foreach(Tuple<int,int> it in gr[curr]) { pq.Add(new Tuple<int,int>(dist ^ it.Item2, it.Item1)); } } // If no path exists return -1; } // Driver code static void Main() { int n = 3; // Graph as adjacency matrix List<List<Tuple<int,int>>> gr = new List<List<Tuple<int,int>>>(); for(int i = 0; i < n + 1; i++) { gr.Add(new List<Tuple<int,int>>()); } // Input edges gr[1].Add(new Tuple<int,int>(3, 9)); gr[2].Add(new Tuple<int,int>(3, 1)); gr[1].Add(new Tuple<int,int>(2, 5)); // Source and destination int s = 1; int d = 3; Console.WriteLine(minXorSumOfEdges(s, d, gr)); }}// This code is contributed by divyesh072019. |
Javascript
<script>// Javascript implementation of the approach// Function to return the smallest// xor sum of edgesfunction minXorSumOfEdges(s, d, gr){ // If the source is equal // to the destination if (s == d) return 0; // Initialise the priority queue let pq = []; pq.push([0, s]); // Visited array let v = new Array(gr.length); // While the priority-queue // is not empty while (pq.length != 0) { pq.sort(function(a, b){return a[0] - b[0];}); // Iterator<Pair> itr = pq.iterator(); // Current node let p = pq.shift(); let curr = p[1]; // Current xor sum of distance let dist = p[0]; // If already visited continue if (v[curr]) continue; // Marking the node as visited v[curr] = true; // If it is a destination node if (curr == d) return dist; // Traversing the current node for(let it = 0; it < gr[curr].length; it++) pq.push([dist ^ gr[curr][it][1], gr[curr][it][0]]); } // If no path exists return -1;}// Driver codelet n = 3; // Graph as adjacency matrixlet gr = [];for(let i = 0; i < n + 1; i++){ gr.push([]);}// Input edgesgr[1].push([3, 9]);gr[2].push([3, 1]);gr[1].push([2, 5]);// Source and destinationlet s = 1, d = 3;document.write(minXorSumOfEdges(s, d, gr));// This code is contributed by unknown2108</script> |
Output:
4
Time complexity: O((E + V) logV)
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!
