Dado un gráfico de N Nodes y E aristas en forma de {U, V, W} tal que existe una arista entre U y V con peso W . Se le da un número entero K y fuente src y destino dst . La tarea es encontrar la ruta de costo más barata desde el origen hasta el destino desde K paradas.
Ejemplos:
Entrada: N = 3, bordes = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 1 Salida:
200 Explicación
:
El precio más barato es de la ciudad 0 a la ciudad 2. Con solo una parada, solo cuesta 200, que es nuestra salida.
Entrada: N = 3, bordes = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 0 Salida
: 500
Método 1: Uso de la búsqueda en profundidad primero
- Explore el Node actual y siga explorando sus elementos secundarios.
- Utilice un mapa para almacenar el Node visitado junto con las paradas y la distancia como valor.
- Rompe el árbol de recurrencia si la clave está presente en el mapa.
- Encuentre la respuesta (costo mínimo) para cada árbol de recurrencia y devuélvala.
A continuación se muestra la implementación de nuestro enfoque.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure to implement hashing to
// stores pairs in map
struct pair_hash {
template <class T1, class T2>
std::size_t
operator()(const std::pair<T1, T2>& pair) const
{
return std::hash<T1>()(pair.first)
^ std::hash<T2>()(pair.second);
}
};
// DFS memoization
vector<vector<int> > adjMatrix;
typedef std::pair<int, int> pair1;
unordered_map<pair1, int, pair_hash> mp;
// Function to implement DFS Traversal
long DFSUtility(int node, int stops,
int dst, int cities)
{
// Base Case
if (node == dst)
return 0;
if (stops < 0) {
return INT_MAX;
}
pair<int, int> key(node, stops);
// Find value with key in a map
if (mp.find(key) != mp.end()) {
return mp[key];
}
long ans = INT_MAX;
// Traverse adjacency matrix of
// source node
for (int neighbour = 0;
neighbour < cities;
++neighbour) {
long weight
= adjMatrix[node][neighbour];
if (weight > 0) {
// Recursive DFS call for
// child node
long minVal
= DFSUtility(neighbour,
stops - 1,
dst, cities);
if (minVal + weight > 0)
ans = min(ans,
minVal
+ weight);
}
}
mp[key] = ans;
// Return ans
return ans;
}
// Function to find the cheapest price
// from given source to destination
int findCheapestPrice(int cities,
vector<vector<int> >& flights,
int src, int dst, int stops)
{
// Resize Adjacency Matrix
adjMatrix.resize(cities + 1,
vector<int>(cities + 1, 0));
// Traverse flight[][]
for (auto item : flights) {
// Create Adjacency Matrix
adjMatrix[item[0]][item[1]] = item[2];
}
// DFS Call to find shortest path
long ans = DFSUtility(src, stops,
dst, cities);
// Return the cost
return ans >= INT_MAX ? -1 : (int)ans;
;
}
// Driver Code
int main()
{
// Input flight : {Source,
// Destination, Cost}
vector<vector<int> > flights
= { { 4, 1, 1 }, { 1, 2, 3 }, { 0, 3, 2 }, { 0, 4, 10 }, { 3, 1, 1 }, { 1, 4, 3 } };
// vec, n, stops, src, dst
int stops = 2;
int totalCities = 5;
int sourceCity = 0;
int destCity = 4;
// Function Call
long ans = findCheapestPrice(
totalCities, flights,
sourceCity, destCity,
stops);
cout << ans;
return 0;
}
Java
// Java program for the above approach
import java.util.HashMap;
public class SingleS {
// DFS memoization
static int adjMatrix[][];
static HashMap<int[], Integer> mp
= new HashMap<int[], Integer>();
// Function to implement DFS Traversal
static int DFSUtility(int node, int stops, int dst,
int cities)
{
// Base Case
if (node == dst)
return 0;
if (stops < 0)
return Integer.MAX_VALUE;
int[] key = new int[] { node, stops };
// Find value with key in a map
if (mp.containsKey(key))
return mp.get(mp);
int ans = Integer.MAX_VALUE;
// Traverse adjacency matrix of
// source node
for (int neighbour = 0; neighbour < cities;
++neighbour) {
int weight = adjMatrix[node][neighbour];
if (weight > 0) {
// Recursive DFS call for
// child node
int minVal = DFSUtility(
neighbour, stops - 1, dst, cities);
if (minVal + weight > 0)
ans = Math.min(ans, minVal + weight);
}
mp.put(key, ans);
}
// Return ans
return ans;
}
// Function to find the cheapest price
// from given source to destination
static int findCheapestPrice(int cities,
int[][] flights, int src,
int dst, int stops)
{
// Resize Adjacency Matrix
adjMatrix = new int[cities + 1][cities + 1];
// Traverse flight[][]
for (int[] item : flights) {
// Create Adjacency Matrix
adjMatrix[item[0]][item[1]] = item[2];
}
// DFS Call to find shortest path
int ans = DFSUtility(src, stops, dst, cities);
// Return the cost
return ans >= Integer.MAX_VALUE ? -1 : ans;
}
// Driver Code
public static void main(String[] args)
{
// Input flight : :Source,
// Destination, Cost
int[][] flights
= { { 4, 1, 1 }, { 1, 2, 3 }, { 0, 3, 2 },
{ 0, 4, 10 }, { 3, 1, 1 }, { 1, 4, 3 } };
// vec, n, stops, src, dst
int stops = 2;
int totalCities = 5;
int sourceCity = 0;
int destCity = 4;
// Function Call
int ans = findCheapestPrice(totalCities, flights,
sourceCity, destCity,
stops);
System.out.println(ans);
}
}
// This code is contributed by Lovely Jain
Python3
# Python3 program for the above approach # DFS memoization adjMatrix=[] mp=dict() # Function to implement DFS Traversal def DFSUtility(node, stops, dst, cities): # Base Case if (node == dst): return 0 if (stops < 0) : return 1e9 key=(node, stops) # Find value with key in a map if key in mp: return mp[key] ans = 1e9 # Traverse adjacency matrix of # source node for neighbour in range(cities): weight = adjMatrix[node][neighbour] if (weight > 0) : # Recursive DFS call for # child node minVal = DFSUtility(neighbour, stops - 1, dst, cities) if (minVal + weight > 0): ans = min(ans, minVal + weight) mp[key] = ans # Return ans return ans # Function to find the cheapest price # from given source to destination def findCheapestPrice(cities, flights, src, dst, stops): global adjMatrix # Resize Adjacency Matrix adjMatrix=[[0]*(cities + 1) for _ in range(cities + 1)] # Traverse flight[][] for item in flights: # Create Adjacency Matrix adjMatrix[item[0]][item[1]] = item[2] # DFS Call to find shortest path ans = DFSUtility(src, stops, dst, cities) # Return the cost return -1 if ans >= 1e9 else int(ans) # Driver Code if __name__ == '__main__': # Input flight : :Source, # Destination, Cost flights = [[ 4, 1, 1 ],[ 1, 2, 3] , [ 0, 3, 2] , [ 0, 4, 10] , [ 3, 1, 1] , [ 1, 4, 3]] # vec, n, stops, src, dst stops = 2 totalCities = 5 sourceCity = 0 destCity = 4 # Function Call ans = findCheapestPrice( totalCities, flights, sourceCity, destCity, stops) print(ans)
C#
// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// DFS memoization
static int[][] adjMatrix;
static Dictionary<int[], int> mp = new Dictionary<int[], int>();
// Function to implement DFS Traversal
static int DFSUtility(int node, int stops, int dst, int cities)
{
// Base Case
if (node == dst){
return 0;
}
if (stops < 0){
return Int32.MaxValue;
}
int[] key = new int[] { node, stops };
// Find value with key in a map
if (mp.ContainsKey(key)){
return mp[key];
}
int ans = Int32.MaxValue;
// Traverse adjacency matrix of
// source node
for (int neighbour = 0 ; neighbour < cities ; ++neighbour) {
int weight = adjMatrix[node][neighbour];
if (weight > 0) {
// Recursive DFS call for
// child node
int minVal = DFSUtility(neighbour, stops - 1, dst, cities);
if (minVal + weight > 0){
ans = Math.Min(ans, minVal + weight);
}
}
if(!mp.ContainsKey(key)){
mp.Add(key, 0);
}
mp[key] = ans;
}
// Return ans
return ans;
}
// Function to find the cheapest price
// from given source to destination
static int findCheapestPrice(int cities, int[][] flights, int src, int dst, int stops)
{
// Resize Adjacency Matrix
adjMatrix = new int[cities + 1][];
for(int i = 0 ; i <= cities ; i++){
adjMatrix[i] = new int[cities + 1];
}
// Traverse flight[][]
foreach (int[] item in flights) {
// Create Adjacency Matrix
adjMatrix[item[0]][item[1]] = item[2];
}
// DFS Call to find shortest path
int ans = DFSUtility(src, stops, dst, cities);
// Return the cost
return ans >= Int32.MaxValue ? -1 : ans;
}
// Driver code
public static void Main(string[] args){
// Input flight : :Source,
// Destination, Cost
int[][] flights = new int[][]{
new int[]{ 4, 1, 1 },
new int[]{ 1, 2, 3 },
new int[]{ 0, 3, 2 },
new int[]{ 0, 4, 10 },
new int[]{ 3, 1, 1 },
new int[]{ 1, 4, 3 }
};
// vec, n, stops, src, dst
int stops = 2;
int totalCities = 5;
int sourceCity = 0;
int destCity = 4;
// Function Call
int ans = findCheapestPrice(totalCities, flights, sourceCity, destCity, stops);
Console.WriteLine(ans);
}
}
// This code is contributed by entertain2022.
Producción:
6
Complejidad Temporal: O(V + E), donde V es el número de Nodes y E son las aristas.
Espacio Auxiliar: O(V)
Método 2: Usar Breadth-FirstSearch
- La idea es usar Queue para realizar BFS Traversal.
- Realice el recorrido desde el Node actual e inserte el Node raíz en la cola.
- Recorra la cola y explore el Node actual y sus hermanos. Luego inserte los hermanos del Node en la cola.
- Mientras explora a cada hermano y siga presionando las entradas en la cola si el costo es menor y actualice el costo mínimo.
- Imprime el costo mínimo después del recorrido anterior.
A continuación se muestra la implementación de nuestro enfoque:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <tuple>
#include <unordered_map>
using namespace std;
// BSF Memoization
typedef tuple<int, int, int> tupl;
// Function to implement BFS
int findCheapestPrice(int cities,
vector<vector<int> >& flights,
int src, int dst, int stops)
{
unordered_map<int,
vector<pair<int, int> > >
adjList;
// Traverse flight[][]
for (auto flight : flights) {
// Create Adjacency Matrix
adjList[flight[0]].push_back(
{ flight[1], flight[2] });
}
// < city, distancefromsource > pair
queue<pair<int, int> >
q;
q.push({ src, 0 });
// Store the Result
int srcDist = INT_MAX;
// Traversing the Matrix
while (!q.empty() && stops-- >= 0) {
int qSize = q.size();
for (int i = 0; i < qSize; i++) {
pair<int, int> curr = q.front();
q.pop();
for (auto next : adjList[curr.first]) {
// If source distance is already
// least the skip this iteration
if (srcDist < curr.second
+ next.second)
continue;
q.push({ next.first,
curr.second
+ next.second });
if (dst == next.first) {
srcDist = min(
srcDist, curr.second
+ next.second);
}
}
}
}
// Returning the Answer
return srcDist == INT_MAX ? -1 : srcDist;
}
// Driver Code
int main()
{
// Input flight : {Source,
// Destination, Cost}
vector<vector<int> > flights
= { { 4, 1, 1 }, { 1, 2, 3 }, { 0, 3, 2 }, { 0, 4, 10 }, { 3, 1, 1 }, { 1, 4, 3 } };
// vec, n, stops, src, dst
int stops = 2;
int totalCities = 5;
// Given source and destination
int sourceCity = 0;
int destCity = 4;
// Function Call
long ans = findCheapestPrice(
totalCities, flights,
sourceCity, destCity,
stops);
cout << ans;
return 0;
}
Python3
# Python3 program of the above approach from queue import Queue as Q # Function to implement BFS def findCheapestPrice(cities, flights, src, dst, stops): adjList=dict() # Traverse flight[][] for flight in flights : # Create Adjacency Matrix if flight[0] in adjList: adjList[flight[0]].append( (flight[1], flight[2])) else: adjList[flight[0]]=[(flight[1], flight[2])] q=Q() q.put((src, 0)) # Store the Result srcDist = 1e9 # Traversing the Matrix while (not q.empty() and stops >= 0) : stops-=1 for i in range(q.qsize()) : curr = q.get() for nxt in adjList[curr[0]]: # If source distance is already # least the skip this iteration if (srcDist < curr[1] + nxt[1]): continue q.put((nxt[0],curr[1] + nxt[1])) if (dst == nxt[0]): srcDist = min( srcDist, curr[1] + nxt[1]) # Returning the Answer return -1 if srcDist == 1e9 else srcDist # Driver Code if __name__ == '__main__': # Input flight : :Source, # Destination, Cost flights= [[ 4, 1, 1 ],[ 1, 2, 3] , [ 0, 3, 2] , [ 0, 4, 10] , [ 3, 1, 1] , [ 1, 4, 3]] # vec, n, stops, src, dst stops = 2 totalCities = 5 # Given source and destination sourceCity = 0 destCity = 4 # Function Call ans = findCheapestPrice( totalCities, flights, sourceCity, destCity, stops) print(ans)
Producción:
6
Complejidad de Tiempo: O(Paradas* N * N) donde N es el Producto de Ciudades y Tamaño en Cola
Espacio Auxiliar: O(N)
Método 3: Uso del algoritmo de Dijkstra
- Actualice la distancia de todos los vértices desde la fuente.
- Los vértices que no están conectados directamente desde la fuente se marcan con infinito y los vértices que están conectados directamente se actualizan con la distancia correcta.
- Comience desde la fuente y extraiga los siguientes vértices mínimos. Esto asegurará el costo mínimo.
- Realice la relajación de borde en cada paso: D denota distancia y w denota pesos
- Si D[u] + w(u, z) < D[z] entonces
- D[z] = D[u] + w(u, z)
Aquí está la implementación de nuestro enfoque:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <tuple>
using namespace std;
typedef tuple<int, int, int> tupl;
long findCheapestPrice(int cities,
vector<vector<int> >& flights,
int src, int dst, int stops)
{
// Adjacency Matrix
vector<vector<pair<int, int> > > adjList(cities);
// Traverse flight[][]
for (auto flight : flights) {
// Create Adjacency Matrix
adjList[flight[0]].push_back(
{ flight[1], flight[2] });
}
// Implementing Priority Queue
priority_queue<tupl, vector<tupl>,
greater<tupl> >
pq;
tupl t = make_tuple(0, src, stops);
pq.push(t);
// While PQ is not empty
while (!pq.empty()) {
tupl t = pq.top();
pq.pop();
if (src == dst)
return 0;
int cost = get<0>(t);
int current = get<1>(t);
int stop = get<2>(t);
if (current == dst)
// Return the Answer
return cost;
if (stop >= 0) {
for (auto next : adjList[current]) {
tupl t = make_tuple((cost
+ next.second),
next.first,
stop - 1);
pq.push(t);
}
}
}
return -1;
}
int main()
{
// Input flight : {Source,
// Destination, Cost}
vector<vector<int> > flights
= { { 4, 1, 1 }, { 1, 2, 3 }, { 0, 3, 2 }, { 0, 4, 10 }, { 3, 1, 1 }, { 1, 4, 3 } };
// vec, n, stops, src, dst
int stops = 2;
int totalCities = 5;
// Given source and destination
int sourceCity = 0;
int destCity = 4;
// Function Call
long ans = findCheapestPrice(
totalCities, flights,
sourceCity, destCity, stops);
cout << ans;
return 0;
}
Python3
# Python3 program for the above approach import heapq as hq def findCheapestPrice(cities, flights, src, dst, stops): # Adjacency Matrix adjList = [[] for _ in range(cities)] # Traverse flight[][] for flight in flights: # Create Adjacency Matrix adjList[flight[0]].append((flight[1], flight[2])) # Implementing Priority Queue pq = [] t = (0, src, stops) hq.heappush(pq, t) # While PQ is not empty while (pq): t = hq.heappop(pq) if (src == dst): return 0 cost, current, stop = t if (current == dst): # Return the Answer return cost if (stop >= 0): for nxt in adjList[current]: t = ((cost + nxt[1]), nxt[0], stop - 1) hq.heappush(pq, t) return -1 if __name__ == '__main__': # Input flight : :Source, # Destination, Cost flights = [[4, 1, 1], [1, 2, 3], [0, 3, 2], [0, 4, 10], [3, 1, 1], [1, 4, 3]] # vec, n, stops, src, dst stops = 2 totalCities = 5 # Given source and destination sourceCity = 0 destCity = 4 # Function Call ans = findCheapestPrice( totalCities, flights, sourceCity, destCity, stops) print(ans)
Producción:
6
Complejidad temporal: O(E+V log V) donde V es el número de Nodes y E son las aristas.
Espacio Auxiliar: O(V)
Método 4: Usando Bellmon Ford
- Inicialice las distancias desde la fuente a todos los vértices como infinito y la distancia a la fuente misma como 0.
- Realice la relajación de borde en cada paso: D denota distancia y w denota pesos
- Si D[u] + w(u, z) < D[z] entonces D[z] = D[u] + w(u, z)
- El algoritmo ha sido modificado para resolver el problema dado en lugar de relajar la gráfica V-1 veces, lo haremos por el número dado de paradas.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program of the above Approach
#include <bits/stdc++.h>
#include <vector>
using namespace std;
// Function to find the cheapest cost
// from source to destination using K stops
int findCheapestPrice(int cities,
vector<vector<int> >& flights,
int src, int dst, int stops)
{
// Distance from source to all other nodes
vector<int> dist(cities, INT_MAX);
dist[src] = 0;
// Do relaxation for V-1 vertices
// here we need for K stops so we
// will do relaxation for k+1 stops
for (int i = 0; i <= stops; i++) {
vector<int> intermediate(dist);
for (auto flight : flights) {
if (dist[flight[0]] != INT_MAX) {
intermediate[flight[1]]
= min(intermediate[flight[1]],
dist[flight[0]]
+ flight[2]);
}
}
// Update the distance vector
dist = intermediate;
}
// Return the final cost
return dist[dst] == INT_MAX ? -1 : dist[dst];
}
// Driver Code
int main()
{
// Input flight : {Source, Destination, Cost}
vector<vector<int> > flights
= { { 4, 1, 1 }, { 1, 2, 3 }, { 0, 3, 2 }, { 0, 4, 10 }, { 3, 1, 1 }, { 1, 4, 3 } };
// vec, n, stops, src, dst
int stops = 2;
int totalCities = 5;
// Given source and destination
int sourceCity = 0;
int destCity = 4;
// Function Call
long ans = findCheapestPrice(
totalCities, flights, sourceCity,
destCity, stops);
cout << ans;
return 0;
}
Python3
# Python3 program of the above Approach # Function to find the cheapest cost # from source to destination using K stops def findCheapestPrice(cities, flights, src, dst, stops): # Distance from source to all other nodes dist=[1e9]*cities dist[src] = 0 # Do relaxation for V-1 vertices # here we need for K stops so we # will do relaxation for k+1 stops for i in range(stops): intermediate=dist for flight in flights: if (dist[flight[0]] != 1e9) : intermediate[flight[1]] = min(intermediate[flight[1]], dist[flight[0]] + flight[2]) # Update the distance vector dist = intermediate # Return the final cost return -1 if dist[dst] == 1e9 else dist[dst] # Driver Code if __name__ == '__main__': # Input flight : :Source, Destination, Cost flights = [[4, 1, 1], [1, 2, 3], [0, 3, 2], [0, 4, 10], [3, 1, 1], [1, 4, 3]] # vec, n, stops, src, dst stops = 2 totalCities = 5 # Given source and destination sourceCity = 0 destCity = 4 # Function Call ans = findCheapestPrice( totalCities, flights, sourceCity, destCity, stops) print(ans)
Producción:
6
Complejidad temporal: O(E*V) donde V es el número de Nodes y E son los bordes.
Espacio Auxiliar: O(V)
Publicación traducida automáticamente
Artículo escrito por priyankachauhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA