Shortest Path in a weighted Graph where weight of an edge is 1 or 2
Given a directed graph where every edge has weight as either 1 or 2, find the shortest path from a given source vertex ‘s’ to a given destination vertex ‘t’. Expected time complexity is O(V+E).
A Simple Solution is to use Dijkstra’s shortest path algorithm, we can get a shortest path in O(E + VLogV) time.
How to do it in O(V+E) time?
The idea is to use BFS. One important observation about BFS is that the path used in BFS always has the least number of edges between any two vertices. So if all edges are of same weight, we can use BFS to find the shortest path. For this problem, we can modify the graph and split all edges of weight 2 into two edges of weight 1 each. We can use BFS to find the shortest path in the modified graph.
How many new intermediate vertices are needed?
We need to add a new intermediate vertex for every source vertex. The reason is simple, if we add an intermediate vertex x between u and v and if we add same vertex between y and z, then new paths u to z and y to v are added to the graph which might have not been there in the original graph. Therefore in a graph with V vertices, we need V extra vertices. Below is the C++ implementation of the above idea. In the below implementation 2*V vertices are created in a graph and for every edge (u, v), we split it into two edges (u, u+V) and (u+V, w). This way, we ensure that a different intermediate vertex is added for every source vertex.
Implementation:
C++
// Program to shortest path from a given source vertex ‘s’ to // a given destination vertex ‘t’. Expected time complexity // is O(V+E). #include<bits/stdc++.h> using namespace std; // This class represents a directed graph using adjacency // list representation class Graph { int V; // No. of vertices list<int> *adj; // adjacency lists public: Graph(int V); // Constructor void addEdge(int v, int w, int weight); // adds an edge // finds shortest path from source vertex ‘s’ to // destination vertex ‘d’. int findShortestPath(int s, int d); // print shortest path from a source vertex ‘s’ to // destination vertex ‘d’. int printShortestPath(int parent[], int s, int d); }; Graph::Graph(int V) { this->V = V; adj = new list<int>[2*V]; } void Graph::addEdge(int v, int w, int weight) { // split all edges of weight 2 into two // edges of weight 1 each. The intermediate // vertex number is maximum vertex number + 1, // that is V. if (weight==2) { adj[v].push_back(v+V); adj[v+V].push_back(w); } else // Weight is 1 adj[v].push_back(w); // Add w to v’s list. } // To print the shortest path stored in parent[] int Graph::printShortestPath(int parent[], int s, int d) { static int level = 0; // If we reached root of shortest path tree if (parent[s] == -1) { cout << "Shortest Path between " << s << " and " << d << " is " << s << " "; return level; } printShortestPath(parent, parent[s], d); level++; if (s < V) cout << s << " "; return level; } // This function mainly does BFS and prints the // shortest path from src to dest. It is assumed // that weight of every edge is 1 int Graph::findShortestPath(int src, int dest) { // Mark all the vertices as not visited bool *visited = new bool[2*V]; int *parent = new int[2*V]; // Initialize parent[] and visited[] for (int i = 0; i < 2*V; i++) { visited[i] = false; parent[i] = -1; } // Create a queue for BFS list<int> queue; // Mark the current node as visited and enqueue it visited[src] = true; queue.push_back(src); // 'i' will be used to get all adjacent vertices of a vertex list<int>::iterator i; while (!queue.empty()) { // Dequeue a vertex from queue and print it int s = queue.front(); if (s == dest) return printShortestPath(parent, s, dest); queue.pop_front(); // Get all adjacent vertices of the dequeued vertex s // If a adjacent has not been visited, then mark it // visited and enqueue it for (i = adj[s].begin(); i != adj[s].end(); ++i) { if (!visited[*i]) { visited[*i] = true; queue.push_back(*i); parent[*i] = s; } } } } // Driver program to test methods of graph class int main() { // Create a graph given in the above diagram int V = 4; Graph g(V); g.addEdge(0, 1, 2); g.addEdge(0, 2, 2); g.addEdge(1, 2, 1); g.addEdge(1, 3, 1); g.addEdge(2, 0, 1); g.addEdge(2, 3, 2); g.addEdge(3, 3, 2); int src = 0, dest = 3; cout << "\nShortest Distance between " << src << " and " << dest << " is " << g.findShortestPath(src, dest); return 0; } |
Java
// Java to shortest path from a given source vertex 's' to // a given destination vertex 't'. Expected time complexity // is O(V+E). import java.util.*;class GFG { // This class represents a directed graph using adjacency // list representation static class Graph { int V; // No. of vertices Vector<Integer>[] adj; // No. of vertices static int level; // Constructor @SuppressWarnings("unchecked") Graph(int V) { this.V = V; this.adj = new Vector[2 * V]; for (int i = 0; i < 2 * V; i++) this.adj[i] = new Vector<>(); } // adds an edge public void addEdge(int v, int w, int weight) { // split all edges of weight 2 into two // edges of weight 1 each. The intermediate // vertex number is maximum vertex number + 1, // that is V. if (weight == 2) { adj[v].add(v + this.V); adj[v + this.V].add(w); } else // Weight is 1 adj[v].add(w); // Add w to v's list. } // print shortest path from a source vertex 's' to // destination vertex 'd'. public int printShortestPath(int[] parent, int s, int d) { level = 0; // If we reached root of shortest path tree if (parent[s] == -1) { System.out.printf("Shortest Path between"+ "%d and %d is %s ", s, d, s); return level; } printShortestPath(parent, parent[s], d); level++; if (s < this.V) System.out.printf("%d ", s); return level; } // finds shortest path from source vertex 's' to // destination vertex 'd'. // This function mainly does BFS and prints the // shortest path from src to dest. It is assumed // that weight of every edge is 1 public int findShortestPath(int src, int dest) { boolean[] visited = new boolean[2 * this.V]; int[] parent = new int[2 * this.V]; // Initialize parent[] and visited[] for (int i = 0; i < 2 * this.V; i++) { visited[i] = false; parent[i] = -1; } // Create a queue for BFS Queue<Integer> queue = new LinkedList<>(); // Mark the current node as visited and enqueue it visited[src] = true; queue.add(src); while (!queue.isEmpty()) { // Dequeue a vertex from queue and print it int s = queue.peek(); if (s == dest) return printShortestPath(parent, s, dest); queue.poll(); // Get all adjacent vertices of the dequeued vertex s // If a adjacent has not been visited, then mark it // visited and enqueue it for (int i : this.adj[s]) { if (!visited[i]) { visited[i] = true; queue.add(i); parent[i] = s; } } } return 0; } } // Driver Code public static void main(String[] args) { // Create a graph given in the above diagram int V = 4; Graph g = new Graph(V); g.addEdge(0, 1, 2); g.addEdge(0, 2, 2); g.addEdge(1, 2, 1); g.addEdge(1, 3, 1); g.addEdge(2, 0, 1); g.addEdge(2, 3, 2); g.addEdge(3, 3, 2); int src = 0, dest = 3; System.out.printf("\nShortest Distance between" + " %d and %d is %d\n", src, dest, g.findShortestPath(src, dest)); }}// This code is contributed by// sanjeev2552 |
Python
''' Program to shortest path from a given source vertex s to a given destination vertex t. Expected time complexity is O(V+E)'''from collections import defaultdict #This class represents a directed graph using adjacency list representationclass Graph: def __init__(self,vertices): self.V = vertices #No. of vertices self.V_org = vertices self.graph = defaultdict(list) # default dictionary to store graph # function to add an edge to graph def addEdge(self,u,v,w): if w == 1: self.graph[u].append(v) else: '''split all edges of weight 2 into two edges of weight 1 each. The intermediate vertex number is maximum vertex number + 1, that is V.''' self.graph[u].append(self.V) self.graph[self.V].append(v) self.V = self.V + 1 # To print the shortest path stored in parent[] def printPath(self, parent, j): Path_len = 1 if parent[j] == -1 and j < self.V_org : #Base Case : If j is source print j, return 0 # when parent[-1] then path length = 0 l = self.printPath(parent , parent[j]) #increment path length Path_len = l + Path_len # print node only if its less than original node length. # i.e do not print any new node that has been added later if j < self.V_org : print j, return Path_len ''' This function mainly does BFS and prints the shortest path from src to dest. It is assumed that weight of every edge is 1''' def findShortestPath(self,src, dest): # Mark all the vertices as not visited # Initialize parent[] and visited[] visited =[False]*(self.V) parent =[-1]*(self.V) # Create a queue for BFS queue=[] # Mark the source node as visited and enqueue it queue.append(src) visited[src] = True while queue : # Dequeue a vertex from queue s = queue.pop(0) # if s = dest then print the path and return if s == dest: return self.printPath(parent, s) # Get all adjacent vertices of the dequeued vertex s # If a adjacent has not been visited, then mark it # visited and enqueue it for i in self.graph[s]: if visited[i] == False: queue.append(i) visited[i] = True parent[i] = s # Create a graph given in the above diagramg = Graph(4)g.addEdge(0, 1, 2)g.addEdge(0, 2, 2)g.addEdge(1, 2, 1)g.addEdge(1, 3, 1)g.addEdge(2, 0, 1)g.addEdge(2, 3, 2)g.addEdge(3, 3, 2)src = 0; dest = 3print ("Shortest Path between %d and %d is " %(src, dest)),l = g.findShortestPath(src, dest)print ("\nShortest Distance between %d and %d is %d " %(src, dest, l)),#This code is contributed by Neelam Yadav |
C#
// C# to shortest path from a given source vertex 's' to // a given destination vertex 't'. Expected time complexity // is O(V+E). using System;using System.Collections.Generic;class GFG { // This class represents a directed graph using adjacency // list representation class Graph { public int V; // No. of vertices public List<int>[] adj; // No. of vertices static int level; // Constructor public Graph(int V) { this.V = V; this.adj = new List<int>[2 * V]; for (int i = 0; i < 2 * V; i++) this.adj[i] = new List<int>(); } // adds an edge public void addEdge(int v, int w, int weight) { // split all edges of weight 2 into two // edges of weight 1 each. The intermediate // vertex number is maximum vertex number + 1, // that is V. if (weight == 2) { adj[v].Add(v + this.V); adj[v + this.V].Add(w); } else // Weight is 1 adj[v].Add(w); // Add w to v's list. } // print shortest path from a source vertex 's' to // destination vertex 'd'. public int printShortestPath(int[] parent, int s, int d) { level = 0; // If we reached root of shortest path tree if (parent[s] == -1) { Console.Write("Shortest Path between"+ "{0} and {1} is {2} ", s, d, s); return level; } printShortestPath(parent, parent[s], d); level++; if (s < this.V) Console.Write("{0} ", s); return level; } // finds shortest path from source vertex 's' to // destination vertex 'd'. // This function mainly does BFS and prints the // shortest path from src to dest. It is assumed // that weight of every edge is 1 public int findShortestPath(int src, int dest) { bool[] visited = new bool[2 * this.V]; int[] parent = new int[2 * this.V]; // Initialize parent[] and visited[] for (int i = 0; i < 2 * this.V; i++) { visited[i] = false; parent[i] = -1; } // Create a queue for BFS List<int> queue = new List<int>(); // Mark the current node as visited and enqueue it visited[src] = true; queue.Add(src); while (queue.Count != 0) { // Dequeue a vertex from queue and print it int s = queue[0]; if (s == dest) return printShortestPath(parent, s, dest); queue.RemoveAt(0); // Get all adjacent vertices of the dequeued vertex s // If a adjacent has not been visited, then mark it // visited and enqueue it foreach (int i in this.adj[s]) { if (!visited[i]) { visited[i] = true; queue.Add(i); parent[i] = s; } } } return 0; } } // Driver Code public static void Main(String[] args) { // Create a graph given in the above diagram int V = 4; Graph g = new Graph(V); g.addEdge(0, 1, 2); g.addEdge(0, 2, 2); g.addEdge(1, 2, 1); g.addEdge(1, 3, 1); g.addEdge(2, 0, 1); g.addEdge(2, 3, 2); g.addEdge(3, 3, 2); int src = 0, dest = 3; Console.Write("\nShortest Distance between" + " {0} and {1} is {2}\n", src, dest, g.findShortestPath(src, dest)); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript program to find shortest path // from a given source vertex 's' to// a given destination vertex 't'. Expected time complexity// is O(V+E).// This class represents a directed graph using adjacency// list representationclass Graph{ constructor(V) { this.V = V; this.adj = new Array(2 * V); this.level = 0; for (let i = 0; i < 2 * V; i++) this.adj[i] = []; } // adds an edge addEdge(v, w, weight) { // split all edges of weight 2 into two // edges of weight 1 each. The intermediate // vertex number is maximum vertex number + 1, // that is V. if (weight == 2) { this.adj[v].push(v + this.V); this.adj[v + this.V].push(w); } else // Weight is 1 this.adj[v].push(w); // Add w to v's list. } // print shortest path from a source vertex 's' to // destination vertex 'd'. printShortestPath(parent, s, d) { this.level = 0; // If we reached root of shortest path tree if (parent[s] == -1) { document.write("Shortest Path between " + s + " and " + d + " is " + s + " "); return this.level; } this.printShortestPath(parent, parent[s], d); this.level++; if (s < this.V) document.write(s + " "); return this.level; } // finds shortest path from source vertex 's' to // destination vertex 'd'. // This function mainly does BFS and prints the // shortest path from src to dest. It is assumed // that weight of every edge is 1 findShortestPath(src, dest) { let visited = new Array(2 * this.V); let parent = new Array(2 * this.V); // Initialize parent[] and visited[] for (let i = 0; i < 2 * this.V; i++) { visited[i] = false; parent[i] = -1; } // Create a queue for BFS let queue = []; // Mark the current node as visited and enqueue it visited[src] = true; queue.push(src); while (queue.length > 0) { // Dequeue a vertex from queue and print it let s = queue[0]; if (s == dest) return this.printShortestPath(parent, s, dest); queue.shift(); // Get all adjacent vertices of the dequeued vertex s // If a adjacent has not been visited, then mark it // visited and enqueue it this.adj[s].forEach(i => { if (!visited[i]){ visited[i] = true; queue.push(i); parent[i] = s; } }); } return 0; }}// Driver Code// Create a graph given in the above diagramlet V = 4;let g = new Graph(V);g.addEdge(0, 1, 2);g.addEdge(0, 2, 2);g.addEdge(1, 2, 1);g.addEdge(1, 3, 1);g.addEdge(2, 0, 1);g.addEdge(2, 3, 2);g.addEdge(3, 3, 2);let src = 0, dest = 3;document.write("<br />Shortest Distance between " + src + " and " + dest + " is " + g.findShortestPath(src, dest));// This code is contributed by cavi4762</script> |
Output
Shortest Path between 0 and 3 is 0 1 3 Shortest Distance between 0 and 3 is 3
Time Complexity: O(V + E)
In this algorithm, we do a Breadth First Traversal of the given graph.
The time complexity of BFS is O(V + E) where V is the number of vertices and E is the number of edges in the graph.
Space Complexity: O(V)
The space complexity for this algorithm is O(V), where V is the number of vertices in the graph.
We need to store the visited array of size V and a parent array of size V.
How is this approach O(V+E)? In worst case, all edges are of weight 2 and we need to do O(E) operations to split all edges and 2V vertices, so the time complexity becomes O(E) + O(V+E) which is O(V+E). This article is contributed by Aditya Goel.
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
