Dado un gráfico dirigido , que puede contener ciclos, donde cada borde tiene peso , la tarea es encontrar el costo mínimo de cualquier camino simple desde un vértice de origen dado ‘s’ a un vértice de destino dado ‘t’. Ruta simple es la ruta de un vértice a otro de modo que ningún vértice se visita más de una vez. Si no hay una ruta simple posible, devuelva INF (infinito).
El gráfico se da como una representación de array de adyacencia donde el valor del gráfico[i][j] indica el peso de un borde desde el vértice i hasta el vértice j y un valor INF(infinito) indica que no hay borde desde i hasta j.
Ejemplos:
Input : V = 5, E = 6
s = 0, t = 2
graph[][] = 0 1 2 3 4
0 INF -1 INF 1 INF
1 INF INF -2 INF INF
2 -3 INF INF INF INF
3 INF INF -1 INF INF
4 INF INF INF 2 INF
Output : -3
Explanation :
The minimum cost simple path between 0 and 2 is given by:
0 -----> 1 ------> 2 whose cost is (-1) + (-2) = (-3).
Input : V = 5, E = 6
s = 0, t = 4
graph[][] = 0 1 2 3 4
0 INF -7 INF -2 INF
1 INF INF -11 INF INF
2 INF INF INF INF INF
3 INF INF INF 3 -4
4 INF INF INF INF INF
Output : -6
Explanation :
The minimum cost simple path between 0 and 2 is given by:
0 -----> 3 ------> 4 whose cost is (-2) + (-4) = (-6).
Enfoque:
la idea principal para resolver el problema anterior es atravesar todas las rutas simples de s a t usando una versión modificada de Depth First Search y encontrar la ruta de costo mínimo entre ellas. Una observación importante sobre DFS es que atraviesa una ruta a la vez, por lo tanto, podemos recorrer rutas separadas de forma independiente utilizando DFS marcando los Nodes como no visitados antes de abandonarlos.
Una solución simple es comenzar desde s, ir a todos los vértices adyacentes y seguir la recursión para más vértices adyacentes hasta llegar al destino. Este algoritmo funcionará incluso cuando los ciclos de peso negativos o los bordes propios estén presentes en el gráfico.
A continuación se muestra la implementación del enfoque mencionado anteriormente:
C++
// C++ code for printing Minimum Cost
// Simple Path between two given nodes
// in a directed and weighted graph
#include <bits/stdc++.h>
using namespace std;
// Define number of vertices in
// the graph and infinite value
#define V 5
#define INF INT_MAX
// Function to do DFS through the nodes
int minimumCostSimplePath(int u, int destination,
bool visited[], int graph[][V])
{
// check if we find the destination
// then further cost will be 0
if (u == destination)
return 0;
// marking the current node as visited
visited[u] = 1;
int ans = INF;
// traverse through all
// the adjacent nodes
for (int i = 0; i < V; i++) {
if (graph[u][i] != INF && !visited[i]) {
// cost of the further path
int curr = minimumCostSimplePath(i,
destination, visited, graph);
// check if we have reached the destination
if (curr < INF) {
// Taking the minimum cost path
ans = min(ans, graph[u][i] + curr);
}
}
}
// unmarking the current node
// to make it available for other
// simple paths
visited[u] = 0;
// returning the minimum cost
return ans;
}
// driver code
int main()
{
// initialising the graph
int graph[V][V];
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
graph[i][j] = INF;
}
}
// marking all nodes as unvisited
bool visited[V] = { 0 };
// initialising the edges;
graph[0][1] = -1;
graph[0][3] = 1;
graph[1][2] = -2;
graph[2][0] = -3;
graph[3][2] = -1;
graph[4][3] = 2;
// source and destination
int s = 0, t = 2;
// marking the source as visited
visited[s] = 1;
cout << minimumCostSimplePath(s, t,
visited, graph);
return 0;
}
Java
// Java code for printing Minimum Cost
// Simple Path between two given nodes
// in a directed and weighted graph
import java.util.*;
import java.lang.*;
class GFG{
// Define number of vertices in
// the graph and infinite value
static int V = 5;
static int INF = Integer.MAX_VALUE;
// Function to do DFS through the nodes
static int minimumCostSimplePath(int u, int destination,
boolean visited[],
int graph[][])
{
// Check if we find the destination
// then further cost will be 0
if (u == destination)
return 0;
// Marking the current node as visited
visited[u] = true;
int ans = INF;
// Traverse through all
// the adjacent nodes
for(int i = 0; i < V; i++)
{
if (graph[u][i] != INF && !visited[i])
{
// Cost of the further path
int curr = minimumCostSimplePath(i,
destination, visited, graph);
// Check if we have reached the
// destination
if (curr < INF)
{
// Taking the minimum cost path
ans = Math.min(ans, graph[u][i] + curr);
}
}
}
// Unmarking the current node
// to make it available for other
// simple paths
visited[u] = false;
// Returning the minimum cost
return ans;
}
// Driver code
public static void main(String[] args)
{
// Initialising the graph
int graph[][] = new int[V][V];
for(int i = 0; i < V; i++)
{
for(int j = 0; j < V; j++)
{
graph[i][j] = INF;
}
}
// Marking all nodes as unvisited
boolean visited[] = new boolean[V];
// Initialising the edges;
graph[0][1] = -1;
graph[0][3] = 1;
graph[1][2] = -2;
graph[2][0] = -3;
graph[3][2] = -1;
graph[4][3] = 2;
// Source and destination
int s = 0, t = 2;
// Marking the source as visited
visited[s] = true;
System.out.println(minimumCostSimplePath(s, t,
visited, graph));
}
}
// This code is contributed by offbeat
Python3
# Python3 code for printing Minimum Cost # Simple Path between two given nodes # in a directed and weighted graph import sys V = 5 INF = sys.maxsize # Function to do DFS through the nodes def minimumCostSimplePath(u, destination, visited, graph): # Check if we find the destination # then further cost will be 0 if (u == destination): return 0 # Marking the current node as visited visited[u] = 1 ans = INF # Traverse through all # the adjacent nodes for i in range(V): if (graph[u][i] != INF and not visited[i]): # Cost of the further path curr = minimumCostSimplePath(i, destination, visited, graph) # Check if we have reached the destination if (curr < INF): # Taking the minimum cost path ans = min(ans, graph[u][i] + curr) # Unmarking the current node # to make it available for other # simple paths visited[u] = 0 # Returning the minimum cost return ans # Driver code if __name__=="__main__": # Initialising the graph graph = [[INF for j in range(V)] for i in range(V)] # Marking all nodes as unvisited visited = [0 for i in range(V)] # Initialising the edges graph[0][1] = -1 graph[0][3] = 1 graph[1][2] = -2 graph[2][0] = -3 graph[3][2] = -1 graph[4][3] = 2 # Source and destination s = 0 t = 2 # Marking the source as visited visited[s] = 1 print(minimumCostSimplePath(s, t, visited, graph)) # This code is contributed by rutvik_56
C#
// C# code for printing Minimum Cost
// Simple Path between two given nodes
// in a directed and weighted graph
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Define number of vertices in
// the graph and infinite value
static int V = 5;
static int INF = int.MaxValue;
// Function to do DFS through the nodes
static int minimumCostSimplePath(int u, int destination,
bool[] visited, int[, ] graph)
{
// Check if we find the destination
// then further cost will be 0
if (u == destination)
return 0;
// Marking the current node as visited
visited[u] = true;
int ans = INF;
// Traverse through all
// the adjacent nodes
for (int i = 0; i < V; i++)
{
if (graph[u, i] != INF && !visited[i])
{
// Cost of the further path
int curr = minimumCostSimplePath(i, destination,
visited, graph);
// Check if we have reached the
// destination
if (curr < INF)
{
// Taking the minimum cost path
ans = Math.Min(ans, graph[u, i] + curr);
}
}
}
// Unmarking the current node
// to make it available for other
// simple paths
visited[u] = false;
// Returning the minimum cost
return ans;
}
// Driver code
public static void Main(string[] args)
{
// Initialising the graph
int[, ] graph = new int[V, V];
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
graph[i, j] = INF;
}
}
// Marking all nodes as unvisited
bool[] visited = new bool[V];
// Initialising the edges;
graph[0, 1] = -1;
graph[0, 3] = 1;
graph[1, 2] = -2;
graph[2, 0] = -3;
graph[3, 2] = -1;
graph[4, 3] = 2;
// Source and destination
int s = 0, t = 2;
// Marking the source as visited
visited[s] = true;
Console.WriteLine(minimumCostSimplePath(s, t, visited, graph));
}
}
// This code is contributed by sanjeev2552
Javascript
<script>
// JavaScript code for printing Minimum Cost
// Simple Path between two given nodes
// in a directed and weighted graph
// Define number of vertices in
// the graph and infinite value
let V = 5
let INF = Number.MAX_SAFE_INTEGER
// Function to do DFS through the nodes
function minimumCostSimplePath(u, destination, visited, graph)
{
// check if we find the destination
// then further cost will be 0
if (u == destination)
return 0;
// marking the current node as visited
visited[u] = 1;
let ans = INF;
// traverse through all
// the adjacent nodes
for (let i = 0; i < V; i++) {
if (graph[u][i] != INF && !visited[i]) {
// cost of the further path
let curr = minimumCostSimplePath(i,
destination, visited, graph);
// check if we have reached the destination
if (curr < INF) {
// Taking the minimum cost path
ans = Math.min(ans, graph[u][i] + curr);
}
}
}
// unmarking the current node
// to make it available for other
// simple paths
visited[u] = 0;
// returning the minimum cost
return ans;
}
// driver code
// initialising the graph
let graph = new Array();
for(let i = 0; i< V; i++){
graph.push([])
}
for (let i = 0; i < V; i++) {
for (let j = 0; j < V; j++) {
graph[i][j] = INF;
}
}
// marking all nodes as unvisited
let visited = new Array(V).fill(0);
// initialising the edges;
graph[0][1] = -1;
graph[0][3] = 1;
graph[1][2] = -2;
graph[2][0] = -3;
graph[3][2] = -1;
graph[4][3] = 2;
// source and destination
let s = 0, t = 2;
// marking the source as visited
visited[s] = 1;
document.write(minimumCostSimplePath(s, t, visited, graph));
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
-3
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA