Verifique si existe una ruta alternativa de U a V con un peso individual más pequeño en un gráfico dado

Dado un gráfico ponderado dirigido con N vértices y M aristas y una arista (U, V) . La tarea es encontrar si hay un camino alternativo presente de U a V con un peso individual de los bordes en el camino alternativo menor que el peso del camino directo. Si está presente, escriba , de lo contrario, escriba No.

Ejemplos  

Para el gráfico dirigido dado: 
 

Entrada: N = 7, M = 10, U = 3, V = 6. 
Salida: No 
Explicación: 
Para el borde dado {3, 6}, peso = 16. No hay un camino alternativo para llegar a 6 desde 3. Por lo tanto, el la respuesta es no

Entrada: N = 7, M = 10, U = 1, V = 6. 
Salida: Sí 
Explicación: 
=> Para el borde dado {1, 6}, peso = 5. 
=> Camino alternativo para llegar a 6 desde 1 = { 1, 5, 6} con pesos individuales {12, 2} que es mayor que 5. Por lo tanto, no se puede considerar este camino. 
=> Camino alternativo para llegar a 6 desde 1 = {1, 2, 4, 5, 6} con pesos individuales {5, 1, 1, 2} que no es menor que 5. Por lo tanto, este camino no se puede considerar. 
=> Camino alternativo para llegar a 6 desde 1 = {1, 4, 5, 6} con pesos individuales {3, 1, 2} que es menor que 5. Por lo tanto, se puede considerar este camino. 
=> Por lo tanto, la respuesta es Sí 

Acercarse:  

  • Atraviese el gráfico dirigido dado con el vértice inicial U utilizando la búsqueda primero en profundidad (DFS) Traversal .
  • Durante DFS Traversal , si el peso de cualquier borde es mayor que el borde dirigido, entonces esa ruta no se incluye.
  • Si alcanzamos el vértice V con el peso de cada borde en la ruta transversal menor que el borde dirigido, entonces existe una ruta alternativa.
  • De lo contrario, no hay camino entre el vértice U y el vértice V que no sea el camino directo.

A continuación se muestra la implementación del enfoque anterior:  

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>
Producción: 

Yes

 

Complejidad temporal: O(N + M), donde N = número de vértices y M = número de aristas.
 

Publicación traducida automáticamente

Artículo escrito por ishan_trivedi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *