Shortest path from source to destination such that edge weights along path are alternatively increasing and decreasing
Given a connected graph with N vertices and M edges. The task is to find the shortest path from source to the destination vertex such that the difference between adjacent edge weights in the shortest path change from positive to negative and vice versa ( Weight(E1) > Weight(E2) < Weight(E3) …. ). If no such path exists then print -1. Examples:
Input: source = 4, destination = 3 Output: 19 4 – 2 – 1 – 3 (Edge Weights: 8, 3, 10) and 4 – 1 – 2 – 3 (Edge Weights: 6, 3, 10) are the only valid paths. Second path takes the minimum cost i.e. 19. Input: source = 2, destination = 4 Output: -1 No such path exists.
Approach: Here, We need to keep two copies of adjacent lists one for positive difference and other for negative difference. Take a Priority Queue as in Dijkstras Algorithm and keep four variables at a time i.e.,
- cost: To store the cost of the path till current node.
- stage: An integer variable to tell what element needs to be taken next, if the previous value was negative then a positive value needs to be taken else take negative.
- weight: Weight of the last visited node.
- vertex: Last visited vertex.
For every vertex push the adjacent vertices based on the required condition (value of stage). See the code for better understanding. Below is the implementation of the above approach:
CPP
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define N 100005 // To store the graph vector<pair< int , int > > incr[N], decr[N]; int _incr[N], _decr[N], shortest[N]; int n, m, src, dest, MAXI = 1LL << 30; // Function to add edges void Add_edge( int x, int y, int w) { incr[x].push_back({ w, y }); incr[y].push_back({ w, x }); decr[x].push_back({ -w, y }); decr[y].push_back({ -w, x }); } // Function to find the shortest distance from // source to destination int Modified_Dijkstra() { // Total cost, stage, weight of previous, vertex priority_queue<pair<pair< int , int >, pair< int , int > > > q; // Sort the edges for ( int i = 1; i <= n; i++) { sort(incr[i].begin(), incr[i].end()); sort(decr[i].begin(), decr[i].end()); } for ( int i = 1; i <= n; i++) shortest[i] = MAXI; // Push the source vertex q.push({ { 0, 0 }, { 0, src } }); while (!q.empty()) { // Take the top element in the queue pair<pair< int , int >, pair< int , int > > FRONT = q.top(); // Remove it from the queue q.pop(); // Store all the values int cost = -FRONT.first.first; int stage = FRONT.first.second; int weight = FRONT.second.first; int v = FRONT.second.second; // Take the minimum cost for the vertex shortest[v] = min(shortest[v], cost); // If destination vertex has already been visited if (shortest[dest] != MAXI) break ; // To make difference negative if (stage) { // Start from last not visited vertex for ( int i = _incr[v]; i < incr[v].size(); i++) { // If we can take the ith vertex if (weight > incr[v][i].first) q.push({ { -(cost + incr[v][i].first), 0 }, { incr[v][i].first, incr[v][i].second } }); else { // To keep the last not visited vertex _incr[v] = i; break ; } } } // To make difference positive else { // Start from last not visited vertex for ( int i = _decr[v]; i < decr[v].size(); i++) { // If we can take the ith vertex if (weight < -decr[v][i].first) q.push({ { -(cost - decr[v][i].first), 1 }, { -decr[v][i].first, decr[v][i].second } }); else { // To keep the last not visited vertex _decr[v] = i; break ; } } } } if (shortest[dest] == MAXI) return -1; return shortest[dest]; } // Driver code int main() { n = 5, src = 4, dest = 3; // Adding edges Add_edge(4, 2, 8); Add_edge(1, 4, 6); Add_edge(2, 3, 10); Add_edge(3, 1, 10); Add_edge(1, 2, 3); Add_edge(3, 5, 3); cout << Modified_Dijkstra(); return 0; } |
Java
/*package whatever //do not write package name here */ import java.util.*; class PQPair { int [] first, second; public PQPair( int [] first, int [] second) { this .first = first; this .second = second; } } public class GFG { static final int N = 100005 ; static List< int []> incr[], decr[]; static int [] _incr, _decr, shortest; static int n, m, src, dest, MAXI = 1 << 30 ; public static void Add_edge( int x, int y, int w) { incr[x].add( new int [] { w, y }); incr[y].add( new int [] { w, x }); decr[x].add( new int [] { -w, y }); decr[y].add( new int [] { -w, x }); } public static int Modified_Dijkstra() { // Total cost, stage, weight of previous, vertex PriorityQueue<PQPair> q = new PriorityQueue<PQPair>( (a, b) -> b.first[ 0 ] - a.first[ 0 ]); // Sort the edges for ( int i = 1 ; i <= n; i++) { Collections.sort(incr[i], (a, b) -> a[ 0 ] != b[ 0 ] ? a[ 0 ] - b[ 0 ] : a[ 1 ] - b[ 1 ]); Collections.sort(decr[i], (a, b) -> a[ 0 ] != b[ 0 ] ? a[ 0 ] - b[ 0 ] : a[ 1 ] - b[ 1 ]); } for ( int i = 1 ; i <= n; i++) shortest[i] = MAXI; // Push the source vertex q.add( new PQPair( new int [] { 0 , 0 }, new int [] { 0 , src })); while (!q.isEmpty()) { // Remove the top element from the queue PQPair FRONT = q.remove(); // Store all the values int cost = -FRONT.first[ 0 ]; int stage = FRONT.first[ 1 ]; int weight = FRONT.second[ 0 ]; int v = FRONT.second[ 1 ]; // Take the minimum cost for the vertex shortest[v] = Math.min(shortest[v], cost); // If destination vertex has already been // visited if (shortest[dest] != MAXI) break ; // To make difference negative if (stage == 1 ) { // Start from last not visited vertex for ( int i = _incr[v]; i < incr[v].size(); i++) { // If we can take the ith vertex if (weight > incr[v].get(i)[ 0 ]) q.add( new PQPair( new int [] { -(cost + incr[v].get(i)[ 0 ]), 0 }, new int [] { incr[v].get(i)[ 0 ], incr[v].get(i)[ 1 ] })); else { // To keep the last not visited // vertex _incr[v] = i; break ; } } } // To make difference positive else { // Start from last not visited vertex for ( int i = _decr[v]; i < decr[v].size(); i++) { // If we can take the ith vertex if (weight < -decr[v].get(i)[ 0 ]) q.add( new PQPair( new int [] { -(cost - decr[v].get(i)[ 0 ]), 1 }, new int [] { -decr[v].get(i)[ 0 ], decr[v].get(i)[ 1 ] })); else { // To keep the last not visited // vertex _decr[v] = i; break ; } } } } if (shortest[dest] == MAXI) return - 1 ; return shortest[dest]; } public static void main(String[] args) { n = 5 ; src = 4 ; dest = 3 ; incr = new ArrayList[n + 1 ]; decr = new ArrayList[n + 1 ]; _incr = new int [n + 1 ]; _decr = new int [n + 1 ]; shortest = new int [n + 1 ]; for ( int i = 0 ; i <= n; i++) { incr[i] = new ArrayList< int []>(); decr[i] = new ArrayList< int []>(); } // Adding edges Add_edge( 4 , 2 , 8 ); Add_edge( 1 , 4 , 6 ); Add_edge( 2 , 3 , 10 ); Add_edge( 3 , 1 , 10 ); Add_edge( 1 , 2 , 3 ); Add_edge( 3 , 5 , 3 ); System.out.println(Modified_Dijkstra()); } } |
Python
import heapq class PriorityQueue: def __init__( self ): self .heap = [] def push( self , item): heapq.heappush( self .heap, item) def pop( self ): return heapq.heappop( self .heap) def is_empty( self ): return len ( self .heap) = = 0 class PQPair: def __init__( self , first, second): self .first = first self .second = second def shortest_path_with_change(adj_pos, adj_neg, src, dest): MAXI = float ( 'inf' ) q = PriorityQueue() q.push(PQPair([ 0 , 0 ], [ 0 , src])) visited = set () while not q.is_empty(): front = q.pop() cost, stage = - front.first[ 0 ], front.first[ 1 ] weight, v = front.second[ 0 ], front.second[ 1 ] if v = = dest: return cost visited.add(v) if stage = = 1 : # Positive difference for w, u in adj_pos[v]: if weight < w and u not in visited: q.push(PQPair([ - cost - w, 0 ], [w, u])) else : # Negative difference for w, u in adj_neg[v]: if weight > w and u not in visited: q.push(PQPair([ - cost + w, 1 ], [w, u])) return - 1 # Example usage: adj_pos = { 1 : [( 1 , 2 )], 2 : [( 3 , 3 )], 3 : [( 5 , 4 )], 4 : [( 2 , 5 )], 5 : [( 1 , 6 )], 6 : [( 4 , 7 )], 7 : [] } # Constructing the negative adjacency list adj_neg = {} for i in range ( 1 , 8 ): adj_neg[i] = [( - w, u) for w, u in adj_pos[i]] src, dest = 1 , 7 # Finding the shortest path with changing differences print (shortest_path_with_change(adj_pos, adj_neg, src, dest)) |
C#
using System; using System.Collections.Generic; using System.Linq; public class PriorityQueue<T> { private List<T> heap; private Comparison<T> comparator; // Constructor public PriorityQueue(Comparison<T> comparator) { heap = new List<T>(); this .comparator = comparator; } // Method to add an element to the priority queue public void Push(T value) { heap.Add(value); heap.Sort(comparator); } // Method to remove and return the element with the highest priority from the priority queue public T Pop() { T frontItem = heap.First(); heap.RemoveAt(0); return frontItem; } // Method to check if the priority queue is empty public bool IsEmpty() { return heap.Count == 0; } } public class PQPair { public int [] First { get ; set ; } public int [] Second { get ; set ; } // Constructor public PQPair( int [] first, int [] second) { First = first; Second = second; } } class Program { // Constants and variables declaration const int N = 100005; static List< int []>[] incr = Enumerable.Range(0, N).Select(_ => new List< int []>()).ToArray(); static List< int []>[] decr = Enumerable.Range(0, N).Select(_ => new List< int []>()).ToArray(); static int [] _incr = new int [N]; static int [] _decr = new int [N]; static int [] shortest = new int [N]; static int n, src, dest; static int MAXI = 1 << 30; // Function to add edges to the graph static void Add_edge( int x, int y, int w) { incr[x].Add( new int [] { w, y }); incr[y].Add( new int [] { w, x }); decr[x].Add( new int [] { -w, y }); decr[y].Add( new int [] { -w, x }); } // Function implementing the modified Dijkstra algorithm static int Modified_Dijkstra() { // Priority queue to store vertices var q = new PriorityQueue<PQPair>((a, b) => b.First[0] - a.First[0]); // Sort the edges for ( int i = 1; i <= n; i++) { incr[i].Sort((a, b) => (a[0] != b[0]) ? a[0] - b[0] : a[1] - b[1]); decr[i].Sort((a, b) => (a[0] != b[0]) ? a[0] - b[0] : a[1] - b[1]); } // Initializing shortest distances for ( int i = 1; i <= n; i++) shortest[i] = MAXI; // Push the source vertex q.Push( new PQPair( new int [] { 0, 0 }, new int [] { 0, src })); while (!q.IsEmpty()) { // Remove the top element from the queue var FRONT = q.Pop(); // Store all the values int cost = -FRONT.First[0]; int stage = FRONT.First[1]; int weight = FRONT.Second[0]; int v = FRONT.Second[1]; // Take the minimum cost for the vertex shortest[v] = Math.Min(shortest[v], cost); // If destination vertex has already been visited if (shortest[dest] != MAXI) break ; // To make difference negative if (stage == 1) { // Start from last not visited vertex for ( int i = _incr[v]; i < incr[v].Count; i++) { // If we can take the ith vertex if (weight > incr[v][i][0]) q.Push( new PQPair( new int [] { -cost - incr[v][i][0], 0 }, new int [] { incr[v][i][0], incr[v][i][1] } )); else { // To keep the last not visited vertex _incr[v] = i; break ; } } } // To make difference positive else { // Start from last not visited vertex for ( int i = _decr[v]; i < decr[v].Count; i++) { // If we can take the ith vertex if (weight < -decr[v][i][0]) q.Push( new PQPair( new int [] { -cost + decr[v][i][0], 1 }, new int [] { -decr[v][i][0], decr[v][i][1] } )); else { // To keep the last not visited vertex _decr[v] = i; break ; } } } } if (shortest[dest] == MAXI) return -1; return shortest[dest]; } // Main method static void Main( string [] args) { n = 5; src = 4; dest = 3; // Adding edges to the graph Add_edge(4, 2, 8); Add_edge(1, 4, 6); Add_edge(2, 3, 10); Add_edge(3, 1, 10); Add_edge(1, 2, 3); Add_edge(3, 5, 3); // Calling the modified Dijkstra algorithm and printing the result Console.WriteLine(Modified_Dijkstra()); } } |
Javascript
class PriorityQueue { constructor(comparator) { this .heap = []; this .comparator = comparator; } push(value) { this .heap.push(value); this .heap.sort( this .comparator); } pop() { return this .heap.shift(); } isEmpty() { return this .heap.length === 0; } } class PQPair { constructor(first, second) { this .first = first; this .second = second; } } function Add_edge(x, y, w) { incr[x].push([w, y]); incr[y].push([w, x]); decr[x].push([-w, y]); decr[y].push([-w, x]); } function Modified_Dijkstra() { // Total cost, stage, weight of previous, vertex const q = new PriorityQueue((a, b) => b.first[0] - a.first[0]); // Sort the edges for (let i = 1; i <= n; i++) { incr[i].sort((a, b) => (a[0] !== b[0]) ? a[0] - b[0] : a[1] - b[1]); decr[i].sort((a, b) => (a[0] !== b[0]) ? a[0] - b[0] : a[1] - b[1]); } for (let i = 1; i <= n; i++) shortest[i] = MAXI; // Push the source vertex q.push( new PQPair([0, 0], [0, src])); while (!q.isEmpty()) { // Remove the top element from the queue const FRONT = q.pop(); // Store all the values const cost = -FRONT.first[0]; const stage = FRONT.first[1]; const weight = FRONT.second[0]; const v = FRONT.second[1]; // Take the minimum cost for the vertex shortest[v] = Math.min(shortest[v], cost); // If destination vertex has already been visited if (shortest[dest] !== MAXI) break ; // To make difference negative if (stage === 1) { // Start from last not visited vertex for (let i = _incr[v]; i < incr[v].length; i++) { // If we can take the ith vertex if (weight > incr[v][i][0]) q.push( new PQPair( [-cost - incr[v][i][0], 0], [incr[v][i][0], incr[v][i][1]] )); else { // To keep the last not visited vertex _incr[v] = i; break ; } } } // To make difference positive else { // Start from last not visited vertex for (let i = _decr[v]; i < decr[v].length; i++) { // If we can take the ith vertex if (weight < -decr[v][i][0]) q.push( new PQPair( [-cost + decr[v][i][0], 1], [-decr[v][i][0], decr[v][i][1]] )); else { // To keep the last not visited vertex _decr[v] = i; break ; } } } } if (shortest[dest] === MAXI) return -1; return shortest[dest]; } const n = 5; const src = 4; const dest = 3; const incr = new Array(n + 1).fill( null ).map(() => []); const decr = new Array(n + 1).fill( null ).map(() => []); const _incr = new Array(n + 1).fill(0); const _decr = new Array(n + 1).fill(0); const shortest = new Array(n + 1); const MAXI = 1 << 30; // Adding edges Add_edge(4, 2, 8); Add_edge(1, 4, 6); Add_edge(2, 3, 10); Add_edge(3, 1, 10); Add_edge(1, 2, 3); Add_edge(3, 5, 3); console.log(Modified_Dijkstra()); |
19
Time complexity:
The time complexity of the Modified Dijkstra’s algorithm is O((E+V)logV), where E is the number of edges and V is the number of vertices. In this implementation, we are using a priority queue to implement the algorithm, and sorting the edges takes O(ElogE) time. Therefore, the overall time complexity of this implementation is O((E+V)logV + ElogE).
Space complexity:
The space complexity of this implementation is O(E+V), where E is the number of edges and V is the number of vertices.