Hay N estaciones en la ruta de un tren. El tren va desde la estación 0 hasta la N-1. El costo del boleto para todos los pares de estaciones (i, j) se da donde j es mayor que i. Encuentre el costo mínimo para llegar al destino.
Considere el siguiente ejemplo:
Input:
cost[N][N] = { {0, 15, 80, 90},
{INF, 0, 40, 50},
{INF, INF, 0, 70},
{INF, INF, INF, 0}
};
There are 4 stations and cost[i][j] indicates cost to reach j
from i. The entries where j < i are meaningless.
Output:
The minimum cost is 65
The minimum cost can be obtained by first going to station 1
from 0. Then from station 1 to station 3.
El costo mínimo para llegar a N-1 desde 0 se puede escribir recursivamente de la siguiente manera:
minCost(0, N-1) = MIN { cost[0][n-1],
cost[0][1] + minCost(1, N-1),
minCost(0, 2) + minCost(2, N-1),
........,
minCost(0, N-2) + cost[N-2][n-1] }
La siguiente es la implementación de la fórmula recursiva anterior.
C++
// A naive recursive solution to find min cost path from station 0
// to station N-1
#include<iostream>
#include<climits>
using namespace std;
// infinite value
#define INF INT_MAX
// Number of stations
#define N 4
// A C++ recursive function to find the shortest path from
// source 's' to destination 'd'.
int minCostRec(int cost[][N], int s, int d)
{
// If source is same as destination
// or destination is next to source
if (s == d || s+1 == d)
return cost[s][d];
// Initialize min cost as direct ticket from
// source 's' to destination 'd'.
int min = cost[s][d];
// Try every intermediate vertex to find minimum
for (int i = s+1; i<d; i++)
{
int c = minCostRec(cost, s, i) +
minCostRec(cost, i, d);
if (c < min)
min = c;
}
return min;
}
// This function returns the smallest possible cost to
// reach station N-1 from station 0. This function mainly
// uses minCostRec().
int minCost(int cost[][N])
{
return minCostRec(cost, 0, N-1);
}
// Driver program to test above function
int main()
{
int cost[N][N] = { {0, 15, 80, 90},
{INF, 0, 40, 50},
{INF, INF, 0, 70},
{INF, INF, INF, 0}
};
cout << "The Minimum cost to reach station "
<< N << " is " << minCost(cost);
return 0;
}
Java
// A Java naive recursive solution to find min cost path from station 0
// to station N-1
class shortest_path
{
static int INF = Integer.MAX_VALUE,N = 4;
// A recursive function to find the shortest path from
// source 's' to destination 'd'.
static int minCostRec(int cost[][], int s, int d)
{
// If source is same as destination
// or destination is next to source
if (s == d || s+1 == d)
return cost[s][d];
// Initialize min cost as direct ticket from
// source 's' to destination 'd'.
int min = cost[s][d];
// Try every intermediate vertex to find minimum
for (int i = s+1; i<d; i++)
{
int c = minCostRec(cost, s, i) +
minCostRec(cost, i, d);
if (c < min)
min = c;
}
return min;
}
// This function returns the smallest possible cost to
// reach station N-1 from station 0. This function mainly
// uses minCostRec().
static int minCost(int cost[][])
{
return minCostRec(cost, 0, N-1);
}
public static void main(String args[])
{
int cost[][] = { {0, 15, 80, 90},
{INF, 0, 40, 50},
{INF, INF, 0, 70},
{INF, INF, INF, 0}
};
System.out.println("The Minimum cost to reach station "+ N+
" is "+minCost(cost));
}
}/* This code is contributed by Rajat Mishra */
Python3
# Python program to find min cost path
# from station 0 to station N-1
global N
N = 4
def minCostRec(cost, s, d):
if s == d or s+1 == d:
return cost[s][d]
min = cost[s][d]
for i in range(s+1, d):
c = minCostRec(cost,s, i) + minCostRec(cost, i, d)
if c < min:
min = c
return min
def minCost(cost):
return minCostRec(cost, 0, N-1)
cost = [ [0, 15, 80, 90],
[float("inf"), 0, 40, 50],
[float("inf"), float("inf"), 0, 70],
[float("inf"), float("inf"), float("inf"), 0]
]
print ("The Minimum cost to reach station %d is %d" % \
(N, minCost(cost)))
# This code is contributed by Divyanshu Mehta
C#
// A C# naive recursive solution to find min
// cost path from station 0 to station N-1
using System;
class GFG {
static int INF = int.MaxValue, N = 4;
// A recursive function to find the
// shortest path from source 's' to
// destination 'd'.
static int minCostRec(int [,]cost, int s, int d)
{
// If source is same as destination
// or destination is next to source
if (s == d || s + 1 == d)
return cost[s,d];
// Initialize min cost as direct
// ticket from source 's' to
// destination 'd'.
int min = cost[s,d];
// Try every intermediate vertex to
// find minimum
for (int i = s + 1; i < d; i++)
{
int c = minCostRec(cost, s, i) +
minCostRec(cost, i, d);
if (c < min)
min = c;
}
return min;
}
// This function returns the smallest
// possible cost to reach station N-1
// from station 0. This function mainly
// uses minCostRec().
static int minCost(int [,]cost)
{
return minCostRec(cost, 0, N-1);
}
// Driver code
public static void Main()
{
int [,]cost = { {0, 15, 80, 90},
{INF, 0, 40, 50},
{INF, INF, 0, 70},
{INF, INF, INF, 0} };
Console.WriteLine("The Minimum cost to"
+ " reach station "+ N
+ " is "+minCost(cost));
}
}
// This code is contributed by Sam007.
PHP
<?php
// A PHP naive recursive solution to find min cost path from station 0
// to station N-1
// infinite value
$INF= PHP_INT_MAX ;
// Number of stations
$N = 4;
// A recursive function to find the shortest path from
// source 's' to destination 'd'.
function minCostRec($cost, $s, $d)
{
// If source is same as destination
// or destination is next to source
if ($s == $d || $s+1 == $d)
return $cost[$s][$d];
// Initialize min cost as direct ticket from
// source 's' to destination 'd'.
$min = $cost[$s][$d];
// Try every intermediate vertex to find minimum
for ($i = $s+1; $i<$d; $i++)
{
$c = minCostRec($cost, $s, $i) +
minCostRec($cost, $i, $d);
if ($c < $min)
$min = $c;
}
return $min;
}
// This function returns the smallest possible cost to
// reach station N-1 from station 0. This function mainly
// uses minCostRec().
function minCost($cost)
{
global $N;
return minCostRec($cost, 0, $N-1);
}
// Driver program to test above function
$cost = array(array(0, 15, 80, 90),
array(INF, 0, 40, 50),
array(INF, INF, 0, 70),
array(INF, INF, INF, 0)
);
echo "The Minimum cost to reach station ",
$N , " is " , minCost($cost);
?>
Javascript
<script>
// A Javascript naive recursive solution to find min cost path from station 0 to station N-1
let INF = Number.MAX_VALUE,N = 4;
// A recursive function to find the shortest path from
// source 's' to destination 'd'.
function minCostRec(cost, s, d)
{
// If source is same as destination
// or destination is next to source
if (s == d || s+1 == d)
return cost[s][d];
// Initialize min cost as direct ticket from
// source 's' to destination 'd'.
let min = cost[s][d];
// Try every intermediate vertex to find minimum
for (let i = s+1; i<d; i++)
{
let c = minCostRec(cost, s, i) +
minCostRec(cost, i, d);
if (c < min)
min = c;
}
return min;
}
// This function returns the smallest possible cost to
// reach station N-1 from station 0. This function mainly
// uses minCostRec().
function minCost(cost)
{
return minCostRec(cost, 0, N-1);
}
let cost = [ [0, 15, 80, 90],
[INF, 0, 40, 50],
[INF, INF, 0, 70],
[INF, INF, INF, 0]
];
document.write("The Minimum cost to reach station "+ N+
" is "+minCost(cost));
// This code is contributed by decode2207.
</script>
Producción
The Minimum cost to reach station 4 is 65
Producción:
The Minimum cost to reach station 4 is 65
La complejidad temporal de la implementación anterior es exponencial, ya que intenta todos los caminos posibles de 0 a N-1. La solución anterior resuelve los mismos subproblemas varias veces (se puede ver dibujando un árbol de recursión para minCostPathRec(0, 5).
Dado que este problema tiene las dos propiedades de los problemas de programación dinámica (ver this y this ). Al igual que otros problemas típicos de programación dinámica (DP), se pueden evitar los cálculos de los mismos subproblemas almacenando las soluciones a los subproblemas y resolviendo los problemas de forma ascendente. .
Una solución de programación dinámica es crear una tabla 2D y llenar la tabla usando la fórmula recursiva dada arriba. El espacio adicional requerido en esta solución sería O(N 2 ) y la complejidad del tiempo sería O(N 3 )
Podemos resolver este problema usando O(N) espacio extra y O(N 2 ) tiempo. La idea se basa en el hecho de que la array de entrada dada es un gráfico acíclico dirigido (DAG). La ruta más corta en DAG se puede calcular utilizando el enfoque discutido en la publicación a continuación.
Ruta más corta en gráfico acíclico dirigido
Necesitamos hacer menos trabajo aquí en comparación con la publicación mencionada anteriormente, ya que conocemos la clasificación topológica del gráfico. La ordenación topológica de los vértices aquí es 0, 1, …, N-1. La siguiente es la idea una vez que se conoce la ordenación topológica.
La idea del siguiente código es calcular primero el costo mínimo para la estación 1, luego para la estación 2, y así sucesivamente. Estos costos se almacenan en una array dist[0…N-1].
- El costo mínimo para la estación 0 es 0, es decir, dist[0] = 0
- El costo mínimo para la estación 1 es cost[0][1], es decir, dist[1] = cost[0][1]
- El costo mínimo para la estación 2 es mínimo de los siguientes dos.
- dist[0] + costo[0][2]
- dist[1] + costo[1][2]
- El costo mínimo para la estación 3 es mínimo de los siguientes tres.
- dist[0] + costo[0][3]
- dist[1] + costo[1][3]
- dist[2] + costo[2][3]
De manera similar, se calculan dist[4], dist[5], … dist[N-1].
A continuación se muestra la implementación de la idea anterior.
C++
// A Dynamic Programming based solution to find min cost
// to reach station N-1 from station 0.
#include<iostream>
#include<climits>
using namespace std;
#define INF INT_MAX
#define N 4
// This function returns the smallest possible cost to
// reach station N-1 from station 0.
int minCost(int cost[][N])
{
// dist[i] stores minimum cost to reach station i
// from station 0.
int dist[N];
for (int i=0; i<N; i++)
dist[i] = INF;
dist[0] = 0;
// Go through every station and check if using it
// as an intermediate station gives better path
for (int i=0; i<N; i++)
for (int j=i+1; j<N; j++)
if (dist[j] > dist[i] + cost[i][j])
dist[j] = dist[i] + cost[i][j];
return dist[N-1];
}
// Driver program to test above function
int main()
{
int cost[N][N] = { {0, 15, 80, 90},
{INF, 0, 40, 50},
{INF, INF, 0, 70},
{INF, INF, INF, 0}
};
cout << "The Minimum cost to reach station "
<< N << " is " << minCost(cost);
return 0;
}
Java
// A Dynamic Programming based solution to find min cost
// to reach station N-1 from station 0.
class shortest_path
{
static int INF = Integer.MAX_VALUE,N = 4;
// A recursive function to find the shortest path from
// source 's' to destination 'd'.
// This function returns the smallest possible cost to
// reach station N-1 from station 0.
static int minCost(int cost[][])
{
// dist[i] stores minimum cost to reach station i
// from station 0.
int dist[] = new int[N];
for (int i=0; i<N; i++)
dist[i] = INF;
dist[0] = 0;
// Go through every station and check if using it
// as an intermediate station gives better path
for (int i=0; i<N; i++)
for (int j=i+1; j<N; j++)
if (dist[j] > dist[i] + cost[i][j])
dist[j] = dist[i] + cost[i][j];
return dist[N-1];
}
public static void main(String args[])
{
int cost[][] = { {0, 15, 80, 90},
{INF, 0, 40, 50},
{INF, INF, 0, 70},
{INF, INF, INF, 0}
};
System.out.println("The Minimum cost to reach station "+ N+
" is "+minCost(cost));
}
}/* This code is contributed by Rajat Mishra */
Python3
# A Dynamic Programming based
# solution to find min cost
# to reach station N-1
# from station 0.
INF = 2147483647
N = 4
# This function returns the
# smallest possible cost to
# reach station N-1 from station 0.
def minCost(cost):
# dist[i] stores minimum
# cost to reach station i
# from station 0.
dist=[0 for i in range(N)]
for i in range(N):
dist[i] = INF
dist[0] = 0
# Go through every station
# and check if using it
# as an intermediate station
# gives better path
for i in range(N):
for j in range(i+1,N):
if (dist[j] > dist[i] + cost[i][j]):
dist[j] = dist[i] + cost[i][j]
return dist[N-1]
# Driver program to
# test above function
cost= [ [0, 15, 80, 90],
[INF, 0, 40, 50],
[INF, INF, 0, 70],
[INF, INF, INF, 0]]
print("The Minimum cost to reach station ",
N," is ",minCost(cost))
# This code is contributed
# by Anant Agarwal.
C#
// A Dynamic Programming based solution
// to find min cost to reach station N-1
// from station 0.
using System;
class GFG {
static int INF = int.MaxValue, N = 4;
// A recursive function to find the
// shortest path from source 's' to
// destination 'd'.
// This function returns the smallest
// possible cost to reach station N-1
// from station 0.
static int minCost(int [,]cost)
{
// dist[i] stores minimum cost
// to reach station i from
// station 0.
int []dist = new int[N];
for (int i = 0; i < N; i++)
dist[i] = INF;
dist[0] = 0;
// Go through every station and check
// if using it as an intermediate
// station gives better path
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++)
if (dist[j] > dist[i] + cost[i,j])
dist[j] = dist[i] + cost[i,j];
return dist[N-1];
}
public static void Main()
{
int [,]cost = { {0, 15, 80, 90},
{INF, 0, 40, 50},
{INF, INF, 0, 70},
{INF, INF, INF, 0} };
Console.WriteLine("The Minimum cost to"
+ " reach station "+ N
+ " is "+minCost(cost));
}
}
// This code is contributed by Sam007.
PHP
<?php
// A Dynamic Programming based solution to find min cost
// to reach station N-1 from station 0.
$INF =PHP_INT_MAX;
$N = 4;
// This function returns the smallest possible cost to
// reach station N-1 from station 0.
function minCost($cost)
{
global $INF;
global $N;
// dist[i] stores minimum cost to reach station i
// from station 0.
$dist[$N]=array();
for ($i=0; $i<$N; $i++)
$dist[$i] = $INF;
$dist[0] = 0;
// Go through every station and check if using it
// as an intermediate station gives better path
for ($i=0; $i<$N; $i++)
for ( $j=$i+1; $j<$N; $j++)
if ($dist[$j] > $dist[$i] + $cost[$i][$j])
$dist[$j] = $dist[$i] + $cost[$i][$j];
return $dist[$N-1];
}
// Driver program to test above function
$cost =array(array(0, 15, 80, 90),
array(INF, 0, 40, 50),
array(INF, INF, 0, 70),
array(INF, INF, INF, 0));
echo "The Minimum cost to reach station ",
$N , " is ",minCost($cost);
?>
Javascript
<script>
// A Dynamic Programming based solution
// to find min cost to reach station N-1
// from station 0.
let INF = Number.MAX_VALUE, N = 4;
// A recursive function to find the
// shortest path from source 's' to
// destination 'd'.
// This function returns the smallest
// possible cost to reach station N-1
// from station 0.
function minCost(cost)
{
// dist[i] stores minimum cost
// to reach station i from
// station 0.
let dist = new Array(N);
dist.fill(0);
for (let i = 0; i < N; i++)
dist[i] = INF;
dist[0] = 0;
// Go through every station and check
// if using it as an intermediate
// station gives better path
for (let i = 0; i < N; i++)
for (let j = i + 1; j < N; j++)
if (dist[j] > dist[i] + cost[i][j])
dist[j] = dist[i] + cost[i][j];
return dist[N-1];
}
let cost = [ [0, 15, 80, 90],
[INF, 0, 40, 50],
[INF, INF, 0, 70],
[INF, INF, INF, 0] ];
document.write("The Minimum cost to"
+ " reach station "+ N
+ " is "+minCost(cost));
</script>
Producción
The Minimum cost to reach station 4 is 65
Producción:
The Minimum cost to reach station 4 is 65
Complejidad de tiempo: O(n 2 ) (dos bucle for anidado)
Espacio auxiliar: O(n) (ya que estamos almacenando la respuesta en el vector dist)
Este artículo es una contribución de Udit Gupta . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA