Monotonic shortest path from source to destination in Directed Weighted Graph
Given a weighted directed graph with N vertices and M edges, a source src and a destination target, the task is to find the shortest monotonic path (monotonically increasing or decreasing) from the source to the destination. Output -1 if no monotonic path is possible.
Note: All weights are non-negative
Examples:
Input: N = 6, M = 9, src = 1, target = 2
edges = {{1, 3, 1.1}, {1, 5, 2}, {1, 6, 3.3}, {2, 5, 2.7},
{3, 4, 2}, {3, 5, 1.1}, {4, 2, 2.3}, {5, 6, 2.4}, {6, 2, 3}}Output: 5.4
Explanation: There are three monotonic paths in the graph
that originate from vertex 1, which are 1 – 6 – 2 because it is strictly increasing,
and 1 – 3 – 4 – 2, and 1 – 5 – 6 – 2 since both are strictly decreasing.
The shortest one of these paths is 1 – 3 – 4 – 2,
which has a sum of weights equal to 1.1 + 2 + 2.3 = 5.4,
So the output is 5.4.Input: N = 5, M = 5, src = 1, target = 5
edges = {{1, 2, 2.3}, {1, 3, 3.1}, {2, 3, 3.7}, {3, 4, 1.9}, {4, 5, 2.1}}Output: -1
Explanation: No monotonic path exists from vertex 1 to vertex 5.
Approach: To solve the problem follow the below idea:
Run Dijkstra’s algorithm twice: one for increasing shortest paths and another for decreasing shortest paths, and take the shorter path of the two results.
Follow the given steps to solve the problem:
- Run Dijkstra’s algorithm twice for both increasing and decreasing paths.
- While doing Dijkstra’s for decreasing shortest paths:
- Only update the shortest path to a vertex v from vertex u if the weight of the edge from u to v is less than the edge on the shortest path directed towards u.
- Similarly for the increasing shortest paths:
- Only update the shortest path to a vertex v from u, if the edge from u to v is greater than the edge on the shortest path directed towards u.
- While doing Dijkstra’s for decreasing shortest paths:
- If the destination vertex has not yet been reached, then no valid shortest path exists.
- If both passes of Dijkstra’s on increasing and decreasing shortest paths result in no valid paths, then return -1.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h> #include <limits> #include <queue> #include <vector> using namespace std; // Represents a vertex in the graph class Vertex { public : int id; vector< int > adjList; vector< double > adjWeights; // A constructor which accepts the id of the vertex Vertex( int num) : id(num) { } }; // Finds the monotonic shortest path using Dijkstra's // algorithm double shortestPath(vector<Vertex>& vertices, int src, int destination) { int N = vertices.size() - 1; // Stores distance from src and edge on the shortest // path from src vector< double > distTo(N + 1, numeric_limits< double >::max()); vector< double > edgeTo(N + 1, numeric_limits< double >::max()); // Set initial distance from src to the highest value for ( int i = 1; i <= N; i++) { distTo[i] = numeric_limits< double >::max(); } // Monotonic decreasing pass of Dijkstra's distTo[src] = 0.0; edgeTo[src] = numeric_limits< double >::max(); priority_queue<pair< double , int >, vector<pair< double , int > >, greater<pair< double , int > > > pq; pq.push(make_pair(0.0, src)); while (!pq.empty()) { // Take the vertex with the closest current distance // from src pair< double , int > top = pq.top(); pq.pop(); int closest = top.second; for ( int i = 0; i < vertices[closest].adjList.size(); i++) { int neighbor = vertices[closest].adjList[i]; double weight = vertices[closest].adjWeights[i]; // Checks if the edges are decreasing and // whether the current directed edge will create // a shorter path if (weight < edgeTo[closest] && distTo[closest] + weight < distTo[neighbor]) { edgeTo[neighbor] = weight; distTo[neighbor] = distTo[closest] + weight; pq.push( make_pair(distTo[neighbor], neighbor)); } } } // Store the result of the first pass of Dijkstra's double firstPass = distTo[destination]; // Monotonic increasing pass of Dijkstra's for ( int i = 1; i <= N; i++) { distTo[i] = numeric_limits< double >::max(); } distTo[src] = 0.0; edgeTo[src] = 0.0; pq.push(make_pair(0.0, src)); while (!pq.empty()) { // Take the vertex with the closest current distance // from src pair< double , int > top = pq.top(); pq.pop(); int closest = top.second; for ( int i = 0; i < vertices[closest].adjList.size(); i++) { int neighbor = vertices[closest].adjList[i]; double weight = vertices[closest].adjWeights[i]; // Checks if the edges are increasing and // whether the current directed edge will create // a shorter path if (weight > edgeTo[closest] && distTo[closest] + weight < distTo[neighbor]) { edgeTo[neighbor] = weight; distTo[neighbor] = distTo[closest] + weight; pq.push( make_pair(distTo[neighbor], neighbor)); } } } // Store the result of the second pass of Dijkstras double secondPass = distTo[destination]; if (firstPass == DBL_MAX && secondPass == DBL_MAX) return -1; return min(firstPass, secondPass); } // Driver Code int main() { int N = 6, M = 9, src, target; // Create N vertices, numbered 1 to N vector<Vertex> vertices(N + 1, Vertex(0)); for ( int i = 1; i <= N; i++) { vertices[i] = Vertex(i); } // Add M edges to the graph vertices[1].adjList.push_back(3); vertices[1].adjWeights.push_back(1.1); vertices[1].adjList.push_back(5); vertices[1].adjWeights.push_back(2.0); vertices[1].adjList.push_back(6); vertices[1].adjWeights.push_back(3.3); vertices[2].adjList.push_back(5); vertices[2].adjWeights.push_back(2.7); vertices[3].adjList.push_back(4); vertices[3].adjWeights.push_back(2.0); vertices[3].adjList.push_back(5); vertices[3].adjWeights.push_back(1.1); vertices[4].adjList.push_back(2); vertices[4].adjWeights.push_back(2.3); vertices[5].adjList.push_back(6); vertices[5].adjWeights.push_back(2.4); vertices[6].adjList.push_back(2); vertices[6].adjWeights.push_back(3.0); // src and destination vertices src = 1; target = 2; double shortest = shortestPath(vertices, src, target); cout << shortest << endl; return 0; } |
Java
import java.io.*; import java.util.*; // Finds the monotonic shortest path // using Dijkstra's algorithm public class Main { public static void main(String[] args) { int N = 6 ; int M = 9 ; // Create an array of vertices Vertex[] vertices = new Vertex[N + 1 ]; // Create instances of each vertex from 1 to N for ( int i = 1 ; i <= N; i++) vertices[i] = new Vertex(i); vertices[ 1 ].adjList.add( 3 ); vertices[ 1 ].adjWeights.add( 1.1 ); vertices[ 1 ].adjList.add( 5 ); vertices[ 1 ].adjWeights.add( 2.0 ); vertices[ 1 ].adjList.add( 6 ); vertices[ 1 ].adjWeights.add( 3.3 ); vertices[ 2 ].adjList.add( 5 ); vertices[ 2 ].adjWeights.add( 2.7 ); vertices[ 3 ].adjList.add( 4 ); vertices[ 3 ].adjWeights.add( 2.0 ); vertices[ 3 ].adjList.add( 5 ); vertices[ 3 ].adjWeights.add( 1.1 ); vertices[ 4 ].adjList.add( 2 ); vertices[ 4 ].adjWeights.add( 2.3 ); vertices[ 5 ].adjList.add( 6 ); vertices[ 5 ].adjWeights.add( 2.4 ); vertices[ 6 ].adjList.add( 2 ); vertices[ 6 ].adjWeights.add( 3.0 ); // src and destination vertices int src = 1 ; int target = 2 ; System.out.println( shortestPath(vertices, N, src, target)); } public static double shortestPath(Vertex vertices[], int N, int src, int destination) { // Stores distance from src and edge // on the shortest path from src double [] distTo = new double [N + 1 ]; double [] edgeTo = new double [N + 1 ]; // Set initial distance from src // to the highest value for ( int i = 1 ; i <= N; i++) distTo[i] = Double.MAX_VALUE; // Monotonic decreasing pass of dijkstras distTo[src] = 0.0 ; edgeTo[src] = Double.MAX_VALUE; PriorityQueue<Vertex> pq = new PriorityQueue<Vertex>( new Comparator<Vertex>() { public int compare(Vertex a, Vertex b) { return Double.compare(distTo[a.id], distTo[b.id]); } }); // Add the initial src vertex // into the priority queue pq.add(vertices[src]); while (!pq.isEmpty()) { // Take the vertex with the closest // current distance from src Vertex closest = pq.remove(); for ( int i = 0 ; i < closest.adjList.size(); i++) { // Checks if the edges are decreasing and // whether the current directed edge will // create a shorter path if (closest.adjWeights.get(i) < edgeTo[closest.id] && distTo[closest.id] + closest.adjWeights.get(i) < distTo[closest.adjList.get( i)]) { edgeTo[closest.adjList.get(i)] = closest.adjWeights.get(i); distTo[closest.adjList.get(i)] = closest.adjWeights.get(i) + distTo[closest.id]; pq.add( vertices[closest.adjList.get(i)]); } } } // Store the result of the first pass of dijkstras double firstPass = distTo[destination]; // Monotonic increasing pass of dijkstras for ( int i = 1 ; i <= N; i++) distTo[i] = Double.MAX_VALUE; distTo[src] = 0.0 ; edgeTo[src] = 0.0 ; // Add the initial src vertex // into the priority queue pq.add(vertices[src]); while (!pq.isEmpty()) { // Take the vertex with the closest current // distance from src Vertex closest = pq.remove(); for ( int i = 0 ; i < closest.adjList.size(); i++) { // Checks if the edges are increasing and // whether the current directed edge will // create a shorter path if (closest.adjWeights.get(i) > edgeTo[closest.id] && distTo[closest.id] + closest.adjWeights.get(i) < distTo[closest.adjList.get( i)]) { edgeTo[closest.adjList.get(i)] = closest.adjWeights.get(i); distTo[closest.adjList.get(i)] = closest.adjWeights.get(i) + distTo[closest.id]; pq.add( vertices[closest.adjList.get(i)]); } } } // Store the result of the second pass of Dijkstras double secondPass = distTo[destination]; if (firstPass == Double.MAX_VALUE && secondPass == Double.MAX_VALUE) return - 1 ; return Math.min(firstPass, secondPass); } } // Represents a vertex in the graph // id stores the vertex number of the vertex instance // adjList stores the id's of adjacent vertices // adjWeights stores the weights of adjacent vertices with // the same indexing as adjList class Vertex { int id; ArrayList<Integer> adjList; ArrayList<Double> adjWeights; // A constructor which accepts // the id of the vertex public Vertex( int num) { id = num; adjList = new ArrayList<Integer>(); adjWeights = new ArrayList<Double>(); } } |
Python3
import heapq class Vertex: def __init__( self , num): self . id = num self .adjList = [] self .adjWeights = [] def shortestPath(vertices, N, src, destination): # Stores distance from src and edge on the shortest path from src distTo = [ float ( 'inf' )] * (N + 1 ) edgeTo = [ 0.0 ] * (N + 1 ) # Monotonic decreasing pass of Dijkstra's distTo[src] = 0.0 edgeTo[src] = float ( 'inf' ) pq = [] heapq.heappush(pq, (distTo[src], vertices[src])) while pq: # Take the vertex with the closest current distance from src dist, closest = heapq.heappop(pq) for i in range ( len (closest.adjList)): # Checks if the edges are decreasing and whether the current directed edge will create a shorter path if (closest.adjWeights[i] < edgeTo[closest. id ] and distTo[closest. id ] + closest.adjWeights[i] < distTo[closest.adjList[i]]): edgeTo[closest.adjList[i]] = closest.adjWeights[i] distTo[closest.adjList[i]] = closest.adjWeights[i] + distTo[closest. id ] heapq.heappush(pq, (distTo[closest.adjList[i]], vertices[closest.adjList[i]])) # Store the result of the first pass of Dijkstra's firstPass = distTo[destination] # Monotonic increasing pass of Dijkstra's distTo = [ float ( 'inf' )] * (N + 1 ) distTo[src] = 0.0 edgeTo[src] = 0.0 pq = [] heapq.heappush(pq, (distTo[src], vertices[src])) while pq: # Take the vertex with the closest current distance from src dist, closest = heapq.heappop(pq) for i in range ( len (closest.adjList)): # Checks if the edges are increasing and whether the current directed edge will create a shorter path if (closest.adjWeights[i] > edgeTo[closest. id ] and distTo[closest. id ] + closest.adjWeights[i] < distTo[closest.adjList[i]]): edgeTo[closest.adjList[i]] = closest.adjWeights[i] distTo[closest.adjList[i]] = closest.adjWeights[i] + distTo[closest. id ] heapq.heappush(pq, (distTo[closest.adjList[i]], vertices[closest.adjList[i]])) # Store the result of the second pass of Dijkstra's secondPass = distTo[destination] if firstPass = = float ( 'inf' ) and secondPass = = float ( 'inf' ): return - 1 return min (firstPass, secondPass) if __name__ = = "__main__" : N = 6 # Create an array of vertices vertices = [ None ] * (N + 1 ) # Create instances of each vertex from 1 to N for i in range ( 1 , N + 1 ): vertices[i] = Vertex(i) vertices[ 1 ].adjList.append( 3 ) vertices[ 1 ].adjWeights.append( 1.1 ) vertices[ 1 ].adjList.append( 5 ) vertices[ 1 ].adjWeights.append( 2.0 ) vertices[ 1 ].adjList.append( 6 ) vertices[ 1 ].adjWeights.append( 3.3 ) vertices[ 2 ].adjList.append( 5 ) vertices[ 2 ].adjWeights.append( 2.7 ) vertices[ 3 ].adjList.append( 4 ) vertices[ 3 ].adjWeights.append( 2.0 ) vertices[ 3 ].adjList.append( 5 ) vertices[ 3 ].adjWeights.append( 1.1 ) vertices[ 4 ].adjList.append( 2 ) vertices[ 4 ].adjWeights.append( 2.3 ) vertices[ 5 ].adjList.append( 6 ) vertices[ 5 ].adjWeights.append( 2.4 ) vertices[ 6 ].adjList.append( 2 ) vertices[ 6 ].adjWeights.append( 3.0 ) # src and destination vertices src = 1 target = 2 print (shortestPath(vertices, N, src, target)) |
C#
using System; using System.Collections.Generic; class Vertex { public int Id { get ; } public List< int > AdjList { get ; } = new List< int >(); public List< double > AdjWeights { get ; } = new List< double >(); public Vertex( int id) { Id = id; } } class Program { static double ShortestPath(Vertex[] vertices, int N, int src, int destination) { double [] distTo = new double [N + 1]; double [] edgeTo = new double [N + 1]; for ( int i = 1; i <= N; i++) distTo[i] = double .PositiveInfinity; distTo[src] = 0.0; edgeTo[src] = double .PositiveInfinity; PriorityQueue<Tuple< double , Vertex>> pq = new PriorityQueue<Tuple< double , Vertex>>( Comparer<Tuple< double , Vertex>>.Create((a, b) => a.Item1.CompareTo(b.Item1))); pq.Enqueue(Tuple.Create(distTo[src], vertices[src])); while (!pq.IsEmpty) { var pair = pq.Dequeue(); double dist = pair.Item1; Vertex closest = pair.Item2; for ( int i = 0; i < closest.AdjList.Count; i++) { if (closest.AdjWeights[i] < edgeTo[closest.Id] && distTo[closest.Id] + closest.AdjWeights[i] < distTo[closest.AdjList[i]]) { edgeTo[closest.AdjList[i]] = closest.AdjWeights[i]; distTo[closest.AdjList[i]] = closest.AdjWeights[i] + distTo[closest.Id]; pq.Enqueue(Tuple.Create(distTo[closest.AdjList[i]], vertices[closest.AdjList[i]])); } } } double firstPass = distTo[destination]; for ( int i = 1; i <= N; i++) distTo[i] = double .PositiveInfinity; distTo[src] = 0.0; edgeTo[src] = 0.0; pq.Enqueue(Tuple.Create(distTo[src], vertices[src])); while (!pq.IsEmpty) { var pair = pq.Dequeue(); double dist = pair.Item1; Vertex closest = pair.Item2; for ( int i = 0; i < closest.AdjList.Count; i++) { if (closest.AdjWeights[i] > edgeTo[closest.Id] && distTo[closest.Id] + closest.AdjWeights[i] < distTo[closest.AdjList[i]]) { edgeTo[closest.AdjList[i]] = closest.AdjWeights[i]; distTo[closest.AdjList[i]] = closest.AdjWeights[i] + distTo[closest.Id]; pq.Enqueue(Tuple.Create(distTo[closest.AdjList[i]], vertices[closest.AdjList[i]])); } } } double secondPass = distTo[destination]; if (firstPass == double .PositiveInfinity && secondPass == double .PositiveInfinity) return -1; return Math.Min(firstPass, secondPass); } static void Main( string [] args) { int N = 6; Vertex[] vertices = new Vertex[N + 1]; for ( int i = 1; i <= N; i++) vertices[i] = new Vertex(i); vertices[1].AdjList.Add(3); vertices[1].AdjWeights.Add(1.1); vertices[1].AdjList.Add(5); vertices[1].AdjWeights.Add(2.0); vertices[1].AdjList.Add(6); vertices[1].AdjWeights.Add(3.3); vertices[2].AdjList.Add(5); vertices[2].AdjWeights.Add(2.7); vertices[3].AdjList.Add(4); vertices[3].AdjWeights.Add(2.0); vertices[3].AdjList.Add(5); vertices[3].AdjWeights.Add(1.1); vertices[4].AdjList.Add(2); vertices[4].AdjWeights.Add(2.3); vertices[5].AdjList.Add(6); vertices[5].AdjWeights.Add(2.4); vertices[6].AdjList.Add(2); vertices[6].AdjWeights.Add(3.0); int src = 1; int target = 2; Console.WriteLine(ShortestPath(vertices, N, src, target)); } } class PriorityQueue<T> { private List<T> list = new List<T>(); private readonly IComparer<T> comparer; public PriorityQueue(IComparer<T> comparer) { this .comparer = comparer; } public void Enqueue(T item) { list.Add(item); int childIndex = list.Count - 1; while (childIndex > 0) { int parentIndex = (childIndex - 1) / 2; if (comparer.Compare(list[childIndex], list[parentIndex]) >= 0) break ; T tmp = list[childIndex]; list[childIndex] = list[parentIndex]; list[parentIndex] = tmp; childIndex = parentIndex; } } public T Dequeue() { int lastIndex = list.Count - 1; T frontItem = list[0]; list[0] = list[lastIndex]; list.RemoveAt(lastIndex); lastIndex--; int parentIndex = 0; while ( true ) { int leftChildIndex = 2 * parentIndex + 1; int rightChildIndex = 2 * parentIndex + 2; if (leftChildIndex > lastIndex) break ; int childIndex = leftChildIndex; if (rightChildIndex <= lastIndex && comparer.Compare(list[leftChildIndex], list[rightChildIndex]) > 0) childIndex = rightChildIndex; if (comparer.Compare(list[parentIndex], list[childIndex]) <= 0) break ; T tmp = list[parentIndex]; list[parentIndex] = list[childIndex]; list[childIndex] = tmp; parentIndex = childIndex; } return frontItem; } public bool IsEmpty { get { return list.Count == 0; } } } |
Javascript
// Represents a vertex in the graph class Vertex { constructor(num) { this .id = num; this .adjList = []; this .adjWeights = []; } } class PriorityQueue { constructor() { this .queue = []; } push(item, priority) { this .queue.push({ item, priority }); this .queue.sort((a, b) => a.priority - b.priority); } pop() { if ( this .isEmpty()) return null ; return this .queue.shift().item; } isEmpty() { return this .queue.length === 0; } } // Finds the monotonic shortest path using Dijkstra's // algorithm function shortestPath(vertices, src, destination) { const N = vertices.length - 1; // Stores distance from src and edge on the shortest // path from src const distTo = new Array(N + 1).fill(Number.POSITIVE_INFINITY); const edgeTo = new Array(N + 1).fill(Number.POSITIVE_INFINITY); // Set initial distance from src to the highest value for (let i = 1; i <= N; i++) { distTo[i] = Number.POSITIVE_INFINITY; } // Monotonic decreasing pass of Dijkstra's distTo[src] = 0.0; edgeTo[src] = Number.POSITIVE_INFINITY; const pq = new PriorityQueue(); pq.push(src, 0.0); while (!pq.isEmpty()) { // Take the vertex with the closest current distance // from src const closest = pq.pop(); for (let i = 0; i < vertices[closest].adjList.length; i++) { const neighbor = vertices[closest].adjList[i]; const weight = vertices[closest].adjWeights[i]; // Checks if the edges are decreasing and // whether the current directed edge will create // a shorter path if (weight < edgeTo[closest] && distTo[closest] + weight < distTo[neighbor]) { edgeTo[neighbor] = weight; distTo[neighbor] = distTo[closest] + weight; pq.push(neighbor, distTo[neighbor]); } } } // Store the result of the first pass of Dijkstra's const firstPass = distTo[destination]; // Monotonic increasing pass of Dijkstra's for (let i = 1; i <= N; i++) { distTo[i] = Number.POSITIVE_INFINITY; } distTo[src] = 0.0; edgeTo[src] = 0.0; pq.push(src, 0.0); while (!pq.isEmpty()) { // Take the vertex with the closest current distance // from src const closest = pq.pop(); for (let i = 0; i < vertices[closest].adjList.length; i++) { const neighbor = vertices[closest].adjList[i]; const weight = vertices[closest].adjWeights[i]; // Checks if the edges are increasing and // whether the current directed edge will create // a shorter path if (weight > edgeTo[closest] && distTo[closest] + weight < distTo[neighbor]) { edgeTo[neighbor] = weight; distTo[neighbor] = distTo[closest] + weight; pq.push(neighbor, distTo[neighbor]); } } } // Store the result of the second pass of Dijkstras const secondPass = distTo[destination]; if (firstPass === Number.POSITIVE_INFINITY && secondPass === Number.POSITIVE_INFINITY) { return -1; } return Math.min(firstPass, secondPass); } // Driver Code const N = 6; const src = 1; const target = 2; // Create N vertices, numbered 1 to N const vertices = Array.from({ length: N + 1 }, (_, i) => new Vertex(i)); // Add M edges to the graph vertices[1].adjList.push(3); vertices[1].adjWeights.push(1.1); vertices[1].adjList.push(5); vertices[1].adjWeights.push(2.0); vertices[1].adjList.push(6); vertices[1].adjWeights.push(3.3); vertices[2].adjList.push(5); vertices[2].adjWeights.push(2.7); vertices[3].adjList.push(4); vertices[3].adjWeights.push(2.0); vertices[3].adjList.push(5); vertices[3].adjWeights.push(1.1); vertices[4].adjList.push(2); vertices[4].adjWeights.push(2.3); vertices[5].adjList.push(6); vertices[5].adjWeights.push(2.4); vertices[6].adjList.push(2); vertices[6].adjWeights.push(3.0); const shortest = shortestPath(vertices, src, target); console.log(shortest); |
5.4
Time Complexity: O(N log(N) + M)
Auxiliary Space: O(N)