Check if alternate path exists from U to V with smaller individual weight in a given Graph

0 0 8 minutes read

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 class
class 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 code
int 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 approach
 
import java.util.*;
 
// To ignore the unchecked warning
@SuppressWarnings("unchecked")
 
// GfG class
public 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 approach
 
class 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 root
def 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 code
if __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 approach
using System;
using System.Collections.Generic;
 
// GfG class
class 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 vertices
let visited = new Array(100);
 
// Adjacency list representation
    // of the graph
let graph=new Array(100);
 
 // Edge class
class Edge 
{
    constructor(u,v,w)
    {
        this.u = u;
            this.v = v;
            this.w = w;
    }
}
 
// Helper method to
    // initialize graph
function  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 root
function 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 zambiatek!