Ruta de costo mínimo en un gráfico dirigido a través de un conjunto dado de Nodes intermedios

Dado un gráfico dirigido y ponderado G , una array V[] que consta de vértices, la tarea es encontrar la ruta de costo mínimo que pasa por todos los vértices del conjunto V , desde una fuente S dada hasta un destino D .

Ejemplos: 

Entrada: V = {7}, S = 0, D = 6 
 

Salida: 11 
Explicación: Ruta 
mínima 0->7->5->6. 
Por lo tanto, el costo del camino = 3 + 6 + 2 = 11

Entrada: V = {7, 4}, S = 0, D = 6 
 

Salida: 12 
Explicación: Ruta 
mínima 0->7->4->6. 
Por lo tanto el costo del camino = 3 + 5 + 4 = 12 

Enfoque: 
Para resolver el problema, la idea es utilizar el recorrido Breadth-First-Search . BFS se usa generalmente para encontrar las rutas más cortas en el gráfico y la distancia mínima de todos los Nodes desde el origen, los Nodes intermedios y el destino puede calcularse mediante el BFS a partir de estos Nodes.

Siga los pasos a continuación para resolver el problema:  

  • Inicialice minSum a INT_MAX .
  • Atraviese el gráfico desde el Node de origen S utilizando BFS .
  • Marque cada Node vecino de la fuente como la nueva fuente y realice BFS desde ese Node.
  • Una vez que se encuentra el Node de destino D , verifique si se visitan todos los Nodes intermedios o no.
  • Si se visitan todos los Nodes intermedios, actualice minSum y devuelva el valor mínimo.
  • Si no se visitan todos los Nodes intermedios, devuelva minSum .
  • Marque la fuente como no visitada.
  • Imprime el valor final de minSum obtenido.

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

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Stores minimum-cost of path from source
int minSum = INT_MAX;
 
// Function to Perform BFS on graph g
// starting from vertex v
void getMinPathSum(unordered_map<int,
                                 vector<pair<int,
                                             int> > >& graph,
                   vector<bool>& visited,
                   vector<int> necessary,
                   int src, int dest, int currSum)
{
    // If destination is reached
    if (src == dest) {
        // Set flag to true
        bool flag = true;
 
        // Visit all the intermediate nodes
        for (int i : necessary) {
 
            // If any intermediate node
            // is not visited
            if (!visited[i]) {
                flag = false;
                break;
            }
        }
 
        // If all intermediate
        // nodes are visited
        if (flag)
 
            // Update the minSum
            minSum = min(minSum, currSum);
        return;
    }
    else {
 
        // Mark the current node
        // visited
        visited[src] = true;
 
        // Traverse adjacent nodes
        for (auto node : graph[src]) {
 
            if (!visited[node.first]) {
 
                // Mark the neighbour visited
                visited[node.first] = true;
 
                // Find minimum cost path
                // considering the neighbour
                // as the source
                getMinPathSum(graph, visited,
                              necessary, node.first,
                              dest, currSum + node.second);
 
                // Mark the neighbour unvisited
                visited[node.first] = false;
            }
        }
 
        // Mark the source unvisited
        visited[src] = false;
    }
}
 
// Driver Code
int main()
{
    // Stores the graph
    unordered_map<int, vector<pair<int,
                                   int> > >
        graph;
    graph[0] = { { 1, 2 }, { 2, 3 }, { 3, 2 } };
    graph[1] = { { 4, 4 }, { 0, 1 } };
    graph[2] = { { 4, 5 }, { 5, 6 } };
    graph[3] = { { 5, 7 }, { 0, 1 } };
    graph[4] = { { 6, 4 } };
    graph[5] = { { 6, 2 } };
    graph[6] = { { 7, 11 } };
 
    // Number of nodes
    int n = 7;
 
    // Source
    int source = 0;
 
    // Destination
    int dest = 6;
 
    // Keeps a check on visited
    // and unvisited nodes
    vector<bool> visited(n, false);
 
    // Stores intermediate nodes
    vector<int> necessary{ 2, 4 };
 
    getMinPathSum(graph, visited, necessary,
                  source, dest, 0);
 
    // If no path is found
    if (minSum == INT_MAX)
        cout << "-1\n";
    else
        cout << minSum << '\n';
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
     
static class pair
{
    int first, second;
     
    pair(int f, int s)
    {
        this.first = f;
        this.second = s;
    }
}
 
// Stores minimum-cost of path from source
static int minSum = Integer.MAX_VALUE;
 
// Function to Perform BFS on graph g
// starting from vertex v
static void getMinPathSum(Map<Integer, ArrayList<pair>> graph,
                          boolean[] visited,
                          ArrayList<Integer> necessary,
                          int source, int dest, int currSum)
{
     
    // If destination is reached
    if (src == dest)
    {
         
        // Set flag to true
        boolean flag = true;
 
        // Visit all the intermediate nodes
        for(int i : necessary)
        {
             
            // If any intermediate node
            // is not visited
            if (!visited[i])
            {
                flag = false;
                break;
            }
        }
 
        // If all intermediate
        // nodes are visited
        if (flag)
         
            // Update the minSum
            minSum = Math.min(minSum, currSum);
             
        return;
    }
    else
    {
         
        // Mark the current node
        // visited
        visited[src] = true;
 
        // Traverse adjacent nodes
        for(pair node : graph.get(src))
        {
            if (!visited[node.first])
            {
                 
                // Mark the neighbour visited
                visited[node.first] = true;
 
                // Find minimum cost path
                // considering the neighbour
                // as the source
                getMinPathSum(graph, visited,
                              necessary, node.first,
                              dest, currSum + node.second);
 
                // Mark the neighbour unvisited
                visited[node.first] = false;
            }
        }
 
        // Mark the source unvisited
        visited[src] = false;
    }
}
 
// Driver code
public static void main(String[] args)
{
     
    // Stores the graph
    Map<Integer, ArrayList<pair>> graph = new HashMap<>();
 
    for(int i = 0; i <= 6; i++)
        graph.put(i, new ArrayList<pair>());
 
    graph.get(0).add(new pair(1, 2));
    graph.get(0).add(new pair(2, 3));
    graph.get(0).add(new pair(3, 2));
    graph.get(1).add(new pair(4, 4));
    graph.get(1).add(new pair(0, 1));
    graph.get(2).add(new pair(4, 5));
    graph.get(2).add(new pair(5, 6));
    graph.get(3).add(new pair(5, 7));
    graph.get(3).add(new pair(0, 1));
    graph.get(4).add(new pair(6, 4));
    graph.get(5).add(new pair(4, 2));
    graph.get(6).add(new pair(7, 11));
 
    // Number of nodes
    int n = 7;
 
    // Source
    int source = 0;
 
    // Destination
    int dest = 6;
 
    // Keeps a check on visited
    // and unvisited nodes
    boolean[] visited = new boolean[n];
 
    // Stores intermediate nodes
    ArrayList<Integer> necessary = new ArrayList<>(
                                   Arrays.asList(2, 4));
 
    getMinPathSum(graph, visited, necessary,
                  source, dest, 0);
 
    // If no path is found
    if (minSum == Integer.MAX_VALUE)
        System.out.println(-1);
    else
        System.out.println(minSum);
}
}
 
// This code is contributed by offbeat

Python3

# Python3 Program to implement
# the above approach
  
# Stores minimum-cost of path from source
minSum = 1000000000
  
# Function to Perform BFS on graph g
# starting from vertex v
def getMinPathSum(graph, visited, necessary,
                  source, dest, currSum):
     
    global minSum
     
    # If destination is reached
    if (src == dest):
       
        # Set flag to true
        flag = True;
  
        # Visit all the intermediate nodes
        for i in necessary:
  
            # If any intermediate node
            # is not visited
            if (not visited[i]):
                flag = False;
                break;
     
        # If all intermediate
        # nodes are visited
        if (flag):
  
            # Update the minSum
            minSum = min(minSum, currSum);
        return;
     
    else:
  
        # Mark the current node
        # visited
        visited[src] = True;
  
        # Traverse adjacent nodes
        for node in graph[src]:
             
            if not visited[node[0]]:
             
                # Mark the neighbour visited
                visited[node[0]] = True;
 
                # Find minimum cost path
                # considering the neighbour
                # as the source
                getMinPathSum(graph, visited,
                              necessary, node[0],
                              dest, currSum + node[1]);
 
                # Mark the neighbour unvisited
                visited[node[0]] = False;
         
        # Mark the source unvisited
        visited[src] = False;
 
# Driver Code
if __name__=='__main__':
     
    # Stores the graph
    graph=dict()
         
    graph[0] = [ [ 1, 2 ], [ 2, 3 ], [ 3, 2 ] ];
    graph[1] = [ [ 4, 4 ], [ 0, 1 ] ];
    graph[2] = [ [ 4, 5 ], [ 5, 6 ] ];
    graph[3] = [ [ 5, 7 ], [ 0, 1 ] ];
    graph[4] = [ [ 6, 4 ] ];
    graph[5] = [ [ 6, 2 ] ];
    graph[6] = [ [ 7, 11 ] ];
     
    # Number of nodes
    n = 7;
  
    # Source
    source = 0;
  
    # Destination
    dest = 6;
  
    # Keeps a check on visited
    # and unvisited nodes
    visited=[ False for i in range(n + 1)]
  
    # Stores intermediate nodes
    necessary = [ 2, 4 ];
  
    getMinPathSum(graph, visited, necessary,
                  source, dest, 0);
  
    # If no path is found
    if (minSum == 1000000000):
        print(-1)
    else:
        print(minSum)
 
        # This code is contributed by pratham76

C#

// C# program to implement
// the above approach
using System;
using System.Collections;
using System.Collections.Generic;
  
class GFG{
      
class pair
{
    public int first, second;
      
    public pair(int f, int s)
    {
        this.first = f;
        this.second = s;
    }
}
  
// Stores minimum-cost of path from source
static int minSum = 100000000;
  
// Function to Perform BFS on graph g
// starting from vertex v
static void getMinPathSum(Dictionary<int, ArrayList> graph,
                          bool[] visited, ArrayList necessary,
                          int source, int dest, int currSum)
{
      
    // If destination is reached
    if (src == dest)
    {
          
        // Set flag to true
        bool flag = true;
  
        // Visit all the intermediate nodes
        foreach(int i in necessary)
        {
              
            // If any intermediate node
            // is not visited
            if (!visited[i])
            {
                flag = false;
                break;
            }
        }
  
        // If all intermediate
        // nodes are visited
        if (flag)
          
            // Update the minSum
            minSum = Math.Min(minSum, currSum);
              
        return;
    }
    else
    {
          
        // Mark the current node
        // visited
        visited[src] = true;
  
        // Traverse adjacent nodes
        foreach(pair node in graph)
        {
            if (!visited[node.first])
            {
                  
                // Mark the neighbour visited
                visited[node.first] = true;
  
                // Find minimum cost path
                // considering the neighbour
                // as the source
                getMinPathSum(graph, visited,
                              necessary, node.first,
                              dest, currSum + node.second);
  
                // Mark the neighbour unvisited
                visited[node.first] = false;
            }
        }
  
        // Mark the source unvisited
        visited[src] = false;
    }
}
  
// Driver code
public static void Main(string[] args)
{
      
    // Stores the graph
    Dictionary<int, ArrayList> graph = new Dictionary<int, ArrayList>();
  
    for(int i = 0; i <= 6; i++)
        graph[i] = new ArrayList();
  
    graph[0].Add(new pair(1, 2));
    graph[0].Add(new pair(2, 3));
    graph[0].Add(new pair(3, 2));
    graph[1].Add(new pair(4, 4));
    graph[1].Add(new pair(0, 1));
    graph[2].Add(new pair(4, 5));
    graph[2].Add(new pair(5, 6));
    graph[3].Add(new pair(5, 7));
    graph[3].Add(new pair(0, 1));
    graph[4].Add(new pair(6, 4));
    graph[5].Add(new pair(4, 2));
    graph[6].Add(new pair(7, 11));
  
    // Number of nodes
    int n = 7;
  
    // Source
    int source = 0;
  
    // Destination
    int dest = 6;
  
    // Keeps a check on visited
    // and unvisited nodes
    bool[] visited = new bool[n];
  
    // Stores intermediate nodes
    ArrayList necessary = new ArrayList();
    necessary.Add(2);
    necessary.Add(4);
  
    getMinPathSum(graph, visited, necessary, source, dest, 0);
  
    // If no path is found
    if (minSum ==  100000000)
        Console.WriteLine(-1);
    else
        Console.WriteLine(minSum);
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
// Javascript program to implement
// the above approach
      
class pair
{
    constructor(f, s)
    {
        this.first = f;
        this.second = s;
    }
}
  
// Stores minimum-cost of path from source
var minSum = 100000000;
  
// Function to Perform BFS on graph g
// starting from vertex v
function getMinPathSum(graph, visited,necessary, src, dest, currSum)
{
      
    // If destination is reached
    if (src == dest)
    {
          
        // Set flag to true
        var flag = true;
  
        // Visit all the intermediate nodes
        for(var i of necessary)
        {
              
            // If any intermediate node
            // is not visited
            if (!visited[i])
            {
                flag = false;
                break;
            }
        }
  
        // If all intermediate
        // nodes are visited
        if (flag)
          
            // Update the minSum
            minSum = Math.min(minSum, currSum);
              
        return;
    }
    else
    {
          
        // Mark the current node
        // visited
        visited[src] = true;
  
        // Traverse adjacent nodes
        for(var node of graph[src])
        {
            if (!visited[node.first])
            {
                  
                // Mark the neighbour visited
                visited[node.first] = true;
  
                // Find minimum cost path
                // considering the neighbour
                // as the source
                getMinPathSum(graph, visited,
                              necessary, node.first,
                              dest, currSum + node.second);
  
                // Mark the neighbour unvisited
                visited[node.first] = false;
            }
        }
  
        // Mark the source unvisited
        visited[src] = false;
    }
}
  
// Driver code
 
// Stores the graph
var graph = Array.from(Array(7), ()=>Array());
 
graph[0].push(new pair(1, 2));
graph[0].push(new pair(2, 3));
graph[0].push(new pair(3, 2));
graph[1].push(new pair(4, 4));
graph[1].push(new pair(0, 1));
graph[2].push(new pair(4, 5));
graph[2].push(new pair(5, 6));
graph[3].push(new pair(5, 7));
graph[3].push(new pair(0, 1));
graph[4].push(new pair(6, 4));
graph[5].push(new pair(4, 2));
graph[6].push(new pair(7, 11));
 
// Number of nodes
var n = 7;
 
// Source
var source = 0;
 
// Destination
var dest = 6;
 
// Keeps a check on visited
// and unvisited nodes
var visited = Array(n).fill(false);
 
// Stores intermediate nodes
var necessary = [];
necessary.push(2);
necessary.push(4);
 
getMinPathSum(graph, visited, necessary, source, dest, 0);
 
// If no path is found
if (minSum ==  100000000)
    document.write(-1);
else
    document.write(minSum);
 
</script>
Producción: 

12

 

Complejidad temporal: O(N+M) 
Espacio auxiliar: O(N+M)
 

Publicación traducida automáticamente

Artículo escrito por AnshulVerma1 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 *