Given a directed weighted graph with N vertices and M edges and an edge (U, V). The task is to find whether there is an alternate path present from U to V with individual weight of edges in alternate path less than the weight of direct path. If present print Yes else print No.
Examples
For the given directed graph:
Input: N = 7, M = 10, U = 3, V = 6.
Output: No
Explanation:
For the given edge {3, 6}, weight = 16. There is no alternate path to reach 6 from 3. Hence the answer is No.Input: N = 7, M = 10, U = 1, V = 6.
Output: Yes
Explanation:
=> For the given edge {1, 6}, weight = 5.
=> Alternate path to reach 6 from 1 = {1, 5, 6} with individual weights {12, 2} which is more than 5. Hence this path cannot be considered.
=> Alternate path to reach 6 from 1 = {1, 2, 4, 5, 6} with individual weights {5, 1, 1, 2} which is not less than 5. Hence this path cannot be considered.
=> Alternate path to reach 6 from 1 = {1, 4, 5, 6} with individual weights {3, 1, 2} which is less than 5. Hence this path can be considered.
=> Hence the answer is Yes
Approach:
- Traverse the given Directed Graph with starting vertex U using depth-first search (DFS) Traversal.
- During DFS Traversal if weight of any edge is greater than the directed edge, then that path is not included.
- If we reach the vertex V with weight of each edge in traverse path less than directed edge, then there exists an alternate path.
- Else there is no path between vertex U and vertex V other than direct path.
Below is the implementation of the above approach:
C++14
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Edge classclass Edge{ public: int u; int v; int w; // Edge constructor to // initialize edge (u, v) with // weight w Edge(int u, int v, int w) { this->u = u; this->v = v; this->w = w; }};class GFG{ public: // Array to mark already // visited vertices bool *visited; // Adjacency list representation // of the graph vector<Edge *> *graph; // GfG class constructor GFG(int size) { visited = new bool[size]; graph = new vector<Edge *>[size]; } // Depth First Search to traverse // all vertices with weight less // than weight of the dfs root void dfs(int S, int W) { // Marking the vertex visited visited[S] = true; // Traversing adjacent vertex for(Edge *uv : graph[S]) { int ver = uv->v; int w = uv->w; if (!visited[ver] && w < W) dfs(ver, W); } }};// Driver codeint main() { // Number of vertices int N = 7; // Number of edges int M = 10; // Edge to be checked int U_V[] = {3, 6}; // Creating GfG object GFG *obj = new GFG(8); // Creating edges Edge *e0 = new Edge(1, 2, 5); Edge *e1 = new Edge(1, 4, 3); Edge *e2 = new Edge(1, 5, 12); Edge *e3 = new Edge(1, 6, 5); Edge *e4 = new Edge(4, 5, 1); Edge *e5 = new Edge(5, 6, 2); Edge *e6 = new Edge(5, 3, 1); Edge *e7 = new Edge(3, 6, 16); Edge *e8 = new Edge(4, 7, 1); Edge *e9 = new Edge(2, 4, 1); // Adding edges to the graph obj->graph[1].push_back(e0); obj->graph[1].push_back(e1); obj->graph[1].push_back(e2); obj->graph[1].push_back(e3); obj->graph[4].push_back(e4); obj->graph[5].push_back(e5); obj->graph[5].push_back(e6); obj->graph[3].push_back(e7); obj->graph[4].push_back(e8); obj->graph[2].push_back(e9); // DFS traversal from // vertex U obj->dfs(U_V[0], 16); // If there is alternate // path then print YES, // else NO if (obj->visited[U_V[1]]) { cout << "NO" << endl; } else { cout << "YES" << endl; }}// This code is contributed by sanjeev2552 |
Java
// Java program for above approachimport java.util.*;// To ignore the unchecked warning@SuppressWarnings("unchecked")// GfG classpublic class GfG { // Array to mark already // visited vertices static private boolean visited[]; // Adjacency list representation // of the graph static private ArrayList<Edge> graph[]; // GfG class constructor public GfG(int size) { visited = new boolean[size]; graph = new ArrayList[size]; } // Edge class static class Edge { int u; int v; int w; // Edge constructor to // initialize edge (u, v) with // weight w Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; } } // Helper method to // initialize graph static private void helperInitialize(int size) { for (int i = 0; i < size; i++) { graph[i] = new ArrayList<Edge>(); } } // Depth First Search to traverse // all vertices with weight less // than weight of the dfs root static private void dfs(int S, int W) { // Marking the vertex visited visited[S] = true; // Traversing adjacent vertex for (Edge uv : graph[S]) { int ver = uv.v; int w = uv.w; if (!visited[ver] && w < W) dfs(ver, W); } } // Driver function public static void main(String[] args) { // Number of vertices int N = 7; // Number of edges int M = 10; // Edge to be checked int U_V[] = { 3, 6 }; // Creating GfG object GfG obj = new GfG(8); // Initializing graph helperInitialize(8); // Creating edges Edge e0 = new Edge(1, 2, 5); Edge e1 = new Edge(1, 4, 3); Edge e2 = new Edge(1, 5, 12); Edge e3 = new Edge(1, 6, 5); Edge e4 = new Edge(4, 5, 1); Edge e5 = new Edge(5, 6, 2); Edge e6 = new Edge(5, 3, 1); Edge e7 = new Edge(3, 6, 16); Edge e8 = new Edge(4, 7, 1); Edge e9 = new Edge(2, 4, 1); // Adding edges to the graph graph[1].add(e0); graph[1].add(e1); graph[1].add(e2); graph[1].add(e3); graph[4].add(e4); graph[5].add(e5); graph[5].add(e6); graph[3].add(e7); graph[4].add(e8); graph[2].add(e9); // DFS traversal from // vertex U dfs(U_V[0], 16); // If there is alternate // path then print YES, // else NO if (visited[U_V[1]]) { System.out.print("No"); } else { System.out.print("Yes"); } }} |
Python3
# Python3 program for above approachclass Edge: # Edge constructor to # initialize edge (u, v) with # weight w def __init__(self, u, v, w): self.u = u self.v = v self.w = w# Depth First Search to traverse# all vertices with weight less# than weight of the dfs rootdef dfs(S, W): global visited,graph # Marking the vertex visited visited[S] = True # Traversing adjacent vertex for uv in graph[S]: ver = uv.v w = uv.w if (not visited[ver] and w < W): dfs(ver, W)# Driver codeif __name__ == '__main__': # Number of vertices N = 7 # Number of edges M = 10 # Edge to be checked U_V = [3, 6] # Creating GfG object visited, graph = [False for i in range(8)], [[] for i in range(8)] # Creating edges e0 = Edge(1, 2, 5) e1 = Edge(1, 4, 3) e2 = Edge(1, 5, 12) e3 = Edge(1, 6, 5) e4 = Edge(4, 5, 1) e5 = Edge(5, 6, 2) e6 = Edge(5, 3, 1) e7 = Edge(3, 6, 16) e8 = Edge(4, 7, 1) e9 = Edge(2, 4, 1) # Adding edges to the graph graph[1].append(e0) graph[1].append(e1) graph[1].append(e2) graph[1].append(e3) graph[4].append(e4) graph[5].append(e5) graph[5].append(e6) graph[3].append(e7) graph[4].append(e8) graph[2].append(e9) # DFS traversal from # vertex U dfs(U_V[0], 16) # If there is alternate # path then print YES, # else NO if (visited[U_V[1]]): print("NO") else : print("YES")# This code is contributed by mohit kumar 29 |
C#
// C# program for above approachusing System;using System.Collections.Generic;// GfG classclass GfG{ // Array to mark already // visited vertices static private bool []visited; // Adjacency list representation // of the graph static private List<Edge> []graph; // GfG class constructor public GfG(int size) { visited = new bool[size]; graph = new List<Edge>[size]; } // Edge class class Edge { public int u; public int v; public int w; // Edge constructor to // initialize edge (u, v) with // weight w public Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; } } // Helper method to // initialize graph static private void helperInitialize(int size) { for (int i = 0; i < size; i++) { graph[i] = new List<Edge>(); } } // Depth First Search to traverse // all vertices with weight less // than weight of the dfs root static private void dfs(int S, int W) { // Marking the vertex visited visited[S] = true; // Traversing adjacent vertex foreach (Edge uv in graph[S]) { int ver = uv.v; int w = uv.w; if (!visited[ver] && w < W) dfs(ver, W); } } // Driver function public static void Main(String[] args) { // Edge to be checked int []U_V = { 3, 6 }; // Creating GfG object GfG obj = new GfG(8); // Initializing graph helperInitialize(8); // Creating edges Edge e0 = new Edge(1, 2, 5); Edge e1 = new Edge(1, 4, 3); Edge e2 = new Edge(1, 5, 12); Edge e3 = new Edge(1, 6, 5); Edge e4 = new Edge(4, 5, 1); Edge e5 = new Edge(5, 6, 2); Edge e6 = new Edge(5, 3, 1); Edge e7 = new Edge(3, 6, 16); Edge e8 = new Edge(4, 7, 1); Edge e9 = new Edge(2, 4, 1); // Adding edges to the graph graph[1].Add(e0); graph[1].Add(e1); graph[1].Add(e2); graph[1].Add(e3); graph[4].Add(e4); graph[5].Add(e5); graph[5].Add(e6); graph[3].Add(e7); graph[4].Add(e8); graph[2].Add(e9); // DFS traversal from // vertex U dfs(U_V[0], 16); // If there is alternate // path then print YES, // else NO if (visited[U_V[1]]) { Console.Write("No"); } else { Console.Write("Yes"); } }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program for above approach// Array to mark already // visited verticeslet visited = new Array(100);// Adjacency list representation // of the graphlet graph=new Array(100); // Edge classclass Edge { constructor(u,v,w) { this.u = u; this.v = v; this.w = w; }}// Helper method to // initialize graphfunction helperInitialize(size){ for (let i = 0; i < size; i++) { graph[i] = []; }}// Depth First Search to traverse // all vertices with weight less // than weight of the dfs rootfunction dfs(S,W){ // Marking the vertex visited visited[S] = true; // Traversing adjacent vertex for (let uv=0;uv<graph[S].length;uv++) { let ver = graph[S][uv].v; let w = graph[S][uv].w; if (!visited[ver] && w < W) dfs(ver, W); }}// Driver function// Number of vertices let N = 7; // Number of edges let M = 10; // Edge to be checked let U_V = [ 3, 6 ]; // Initializing graph helperInitialize(8); // Creating edges let e0 = new Edge(1, 2, 5); let e1 = new Edge(1, 4, 3); let e2 = new Edge(1, 5, 12); let e3 = new Edge(1, 6, 5); let e4 = new Edge(4, 5, 1); let e5 = new Edge(5, 6, 2); let e6 = new Edge(5, 3, 1); let e7 = new Edge(3, 6, 16); let e8 = new Edge(4, 7, 1); let e9 = new Edge(2, 4, 1); // Adding edges to the graph graph[1].push(e0); graph[1].push(e1); graph[1].push(e2); graph[1].push(e3); graph[4].push(e4); graph[5].push(e5); graph[5].push(e6); graph[3].push(e7); graph[4].push(e8); graph[2].push(e9); // DFS traversal from // vertex U dfs(U_V[0], 16); // If there is alternate // path then print YES, // else NO if (visited[U_V[1]]) { document.write("No"); } else { document.write("Yes"); }// This code is contributed by unknown2108</script> |
Output:
Yes
Time Complexity: O(N + M), where N = number of vertices & M = number of edges.
Space Complexity: O(N)
The space complexity of the above algorithm is O(N) where N is the number of vertices. This space is used for keeping a visited array for every vertex.
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!
