Dada una dirección y dos vértices ‘u’ y ‘v’ en ella, encuentra el camino más corto de ‘u’ a ‘v’ con exactamente k aristas en el camino.
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.
Por ejemplo, considere el siguiente gráfico. Deje que la fuente ‘u’ sea el vértice 0, el destino ‘v’ sea 3 y k sea 2. Hay dos caminos de longitud 2, los caminos son {0, 2, 3} y {0, 1, 3}. El más corto entre los dos es {0, 2, 3} y el peso de la ruta es 3+6 = 9.
La idea es navegar a través de todos los caminos de longitud k de u a v usando el enfoque discutido en la publicación anterior y devolver el peso del camino más corto. Una solución simple es comenzar desde u, ir a todos los vértices adyacentes y repetir para los vértices adyacentes con k como k-1, el origen como vértice adyacente y el destino como v. Las siguientes son implementaciones en C++ y Java de esta solución simple.
C++
// C++ program to find shortest path with exactly k edges
#include <bits/stdc++.h>
using namespace std;
// Define number of vertices in the graph and infinite value
#define V 4
#define INF INT_MAX
// A naive recursive function to count walks from u to v with k edges
int shortestPath(int graph[][V], int u, int v, int k)
{
// Base cases
if (k == 0 && u == v) return 0;
if (k == 1 && graph[u][v] != INF) return graph[u][v];
if (k <= 0) return INF;
// Initialize result
int res = INF;
// Go to all adjacents of u and recur
for (int i = 0; i < V; i++)
{
if (graph[u][i] != INF && u != i && v != i)
{
int rec_res = shortestPath(graph, i, v, k-1);
if (rec_res != INF)
res = min(res, graph[u][i] + rec_res);
}
}
return res;
}
// driver program to test above function
int main()
{
/* Let us create the graph shown in above diagram*/
int graph[V][V] = { {0, 10, 3, 2},
{INF, 0, INF, 7},
{INF, INF, 0, 6},
{INF, INF, INF, 0}
};
int u = 0, v = 3, k = 2;
cout << "Weight of the shortest path is " <<
shortestPath(graph, u, v, k);
return 0;
}
Java
// Dynamic Programming based Java program to find shortest path
// with exactly k edges
import java.util.*;
import java.lang.*;
import java.io.*;
class ShortestPath
{
// Define number of vertices in the graph and infinite value
static final int V = 4;
static final int INF = Integer.MAX_VALUE;
// A naive recursive function to count walks from u to v
// with k edges
int shortestPath(int graph[][], int u, int v, int k)
{
// Base cases
if (k == 0 && u == v) return 0;
if (k == 1 && graph[u][v] != INF) return graph[u][v];
if (k <= 0) return INF;
// Initialize result
int res = INF;
// Go to all adjacents of u and recur
for (int i = 0; i < V; i++)
{
if (graph[u][i] != INF && u != i && v != i)
{
int rec_res = shortestPath(graph, i, v, k-1);
if (rec_res != INF)
res = Math.min(res, graph[u][i] + rec_res);
}
}
return res;
}
public static void main (String[] args)
{
/* Let us create the graph shown in above diagram*/
int graph[][] = new int[][]{ {0, 10, 3, 2},
{INF, 0, INF, 7},
{INF, INF, 0, 6},
{INF, INF, INF, 0}
};
ShortestPath t = new ShortestPath();
int u = 0, v = 3, k = 2;
System.out.println("Weight of the shortest path is "+
t.shortestPath(graph, u, v, k));
}
}
Python3
# Python3 program to find shortest path
# with exactly k edges
# Define number of vertices in the graph
# and infinite value
# A naive recursive function to count
# walks from u to v with k edges
def shortestPath(graph, u, v, k):
V = 4
INF = 999999999999
# Base cases
if k == 0 and u == v:
return 0
if k == 1 and graph[u][v] != INF:
return graph[u][v]
if k <= 0:
return INF
# Initialize result
res = INF
# Go to all adjacents of u and recur
for i in range(V):
if graph[u][i] != INF and u != i and v != i:
rec_res = shortestPath(graph, i, v, k - 1)
if rec_res != INF:
res = min(res, graph[u][i] + rec_res)
return res
# Driver Code
if __name__ == '__main__':
INF = 999999999999
# Let us create the graph shown
# in above diagram
graph = [[0, 10, 3, 2],
[INF, 0, INF, 7],
[INF, INF, 0, 6],
[INF, INF, INF, 0]]
u = 0
v = 3
k = 2
print("Weight of the shortest path is",
shortestPath(graph, u, v, k))
# This code is contributed by PranchalK
C#
// Dynamic Programming based C# program to
// find shortest pathwith exactly k edges
using System;
class GFG
{
// Define number of vertices in the
// graph and infinite value
const int V = 4;
const int INF = Int32.MaxValue;
// A naive recursive function to count
// walks from u to v with k edges
int shortestPath(int[,] graph, int u,
int v, int k)
{
// Base cases
if (k == 0 && u == v) return 0;
if (k == 1 && graph[u, v] != INF) return graph[u, v];
if (k <= 0) return INF;
// Initialize result
int res = INF;
// Go to all adjacents of u and recur
for (int i = 0; i < V; i++)
{
if (graph[u, i] != INF && u != i && v != i)
{
int rec_res = shortestPath(graph, i, v, k - 1);
if (rec_res != INF)
res = Math.Min(res, graph[u, i] + rec_res);
}
}
return res;
}
// Driver Code
public static void Main ()
{
/* Let us create the graph
shown in above diagram*/
int[,] graph = new int[,]{{0, 10, 3, 2},
{INF, 0, INF, 7},
{INF, INF, 0, 6},
{INF, INF, INF, 0}};
GFG t = new GFG();
int u = 0, v = 3, k = 2;
Console.WriteLine("Weight of the shortest path is "+
t.shortestPath(graph, u, v, k));
}
}
// This code is contributed by Akanksha Rai
Javascript
<script>
// Dynamic Programming based Javascript
// program to find shortest path
// with exactly k edges
// Define number of vertices in the graph and infinite value
let V = 4;
let INF = Number.MAX_VALUE;
// A naive recursive function to count walks from u to v
// with k edges
function shortestPath(graph,u,v,k)
{
// Base cases
if (k == 0 && u == v) return 0;
if (k == 1 && graph[u][v] != INF) return graph[u][v];
if (k <= 0) return INF;
// Initialize result
let res = INF;
// Go to all adjacents of u and recur
for (let i = 0; i < V; i++)
{
if (graph[u][i] != INF && u != i && v != i)
{
let rec_res = shortestPath(graph, i, v, k-1);
if (rec_res != INF)
res = Math.min(res, graph[u][i] + rec_res);
}
}
return res;
}
let graph=[[0, 10, 3, 2],[INF, 0, INF, 7],
[INF, INF, 0, 6],[INF, INF, INF, 0]];
let u = 0, v = 3, k = 2;
document.write("Weight of the shortest path is "+
shortestPath(graph, u, v, k));
// This code is contributed by rag2127
</script>
Producción
Weight of the shortest path is 9
La complejidad temporal en el peor de los casos de la función anterior es O(V k ) donde V es el número de vértices en el gráfico dado. Simplemente podemos analizar la complejidad del tiempo dibujando un árbol de recursión. Lo peor ocurre para un gráfico completo. En el peor de los casos, cada Node interno del árbol de recursión tendría exactamente V hijos.
Podemos optimizar la solución anterior usando Programación Dinámica . La idea es construir una tabla 3D donde la primera dimensión es el origen, la segunda dimensión es el destino, la tercera dimensión es el número de aristas desde el origen hasta el destino, y el valor es el peso del camino más corto que tiene exactamente la cantidad de aristas, almacenado en el tercera dimensión, de origen a destino. Al igual que otros problemas de Programación Dinámica , llenamos la tabla 3D de forma ascendente.
C++
// Dynamic Programming based C++ program to find shortest path with
// exactly k edges
#include <iostream>
#include <climits>
using namespace std;
// Define number of vertices in the graph and infinite value
#define V 4
#define INF INT_MAX
// A Dynamic programming based function to find the shortest path from
// u to v with exactly k edges.
int shortestPath(int graph[][V], int u, int v, int k)
{
// Table to be filled up using DP. The value sp[i][j][e] will store
// weight of the shortest path from i to j with exactly k edges
int sp[V][V][k+1];
// Loop for number of edges from 0 to k
for (int e = 0; e <= k; e++)
{
for (int i = 0; i < V; i++) // for source
{
for (int j = 0; j < V; j++) // for destination
{
// initialize value
sp[i][j][e] = INF;
// from base cases
if (e == 0 && i == j)
sp[i][j][e] = 0;
if (e == 1 && graph[i][j] != INF)
sp[i][j][e] = graph[i][j];
//go to adjacent only when number of edges is more than 1
if (e > 1)
{
for (int a = 0; a < V; a++)
{
// There should be an edge from i to a and a
// should not be same as either i or j
if (graph[i][a] != INF && i != a &&
j!= a && sp[a][j][e-1] != INF)
sp[i][j][e] = min(sp[i][j][e], graph[i][a] +
sp[a][j][e-1]);
}
}
}
}
}
return sp[u][v][k];
}
// driver program to test above function
int main()
{
/* Let us create the graph shown in above diagram*/
int graph[V][V] = { {0, 10, 3, 2},
{INF, 0, INF, 7},
{INF, INF, 0, 6},
{INF, INF, INF, 0}
};
int u = 0, v = 3, k = 2;
cout << shortestPath(graph, u, v, k);
return 0;
}
Java
// Dynamic Programming based Java program to find shortest path with
// exactly k edges
import java.util.*;
import java.lang.*;
import java.io.*;
class ShortestPath
{
// Define number of vertices in the graph and infinite value
static final int V = 4;
static final int INF = Integer.MAX_VALUE;
// A Dynamic programming based function to find the shortest path
// from u to v with exactly k edges.
int shortestPath(int graph[][], int u, int v, int k)
{
// Table to be filled up using DP. The value sp[i][j][e] will
// store weight of the shortest path from i to j with exactly
// k edges
int sp[][][] = new int[V][V][k+1];
// Loop for number of edges from 0 to k
for (int e = 0; e <= k; e++)
{
for (int i = 0; i < V; i++) // for source
{
for (int j = 0; j < V; j++) // for destination
{
// initialize value
sp[i][j][e] = INF;
// from base cases
if (e == 0 && i == j)
sp[i][j][e] = 0;
if (e == 1 && graph[i][j] != INF)
sp[i][j][e] = graph[i][j];
// go to adjacent only when number of edges is
// more than 1
if (e > 1)
{
for (int a = 0; a < V; a++)
{
// There should be an edge from i to a and
// a should not be same as either i or j
if (graph[i][a] != INF && i != a &&
j!= a && sp[a][j][e-1] != INF)
sp[i][j][e] = Math.min(sp[i][j][e],
graph[i][a] + sp[a][j][e-1]);
}
}
}
}
}
return sp[u][v][k];
}
public static void main (String[] args)
{
/* Let us create the graph shown in above diagram*/
int graph[][] = new int[][]{ {0, 10, 3, 2},
{INF, 0, INF, 7},
{INF, INF, 0, 6},
{INF, INF, INF, 0}
};
ShortestPath t = new ShortestPath();
int u = 0, v = 3, k = 2;
System.out.println("Weight of the shortest path is "+
t.shortestPath(graph, u, v, k));
}
}
//This code is contributed by Aakash Hasija
Python3
# Dynamic Programming based Python3
# program to find shortest path with
# A Dynamic programming based function
# to find the shortest path from u to v
# with exactly k edges.
def shortestPath(graph, u, v, k):
global V, INF
# Table to be filled up using DP. The
# value sp[i][j][e] will store weight
# of the shortest path from i to j
# with exactly k edges
sp = [[None] * V for i in range(V)]
for i in range(V):
for j in range(V):
sp[i][j] = [None] * (k + 1)
# Loop for number of edges from 0 to k
for e in range(k + 1):
for i in range(V): # for source
for j in range(V): # for destination
# initialize value
sp[i][j][e] = INF
# from base cases
if (e == 0 and i == j):
sp[i][j][e] = 0
if (e == 1 and graph[i][j] != INF):
sp[i][j][e] = graph[i][j]
# go to adjacent only when number
# of edges is more than 1
if (e > 1):
for a in range(V):
# There should be an edge from
# i to a and a should not be
# same as either i or j
if (graph[i][a] != INF and i != a and
j!= a and sp[a][j][e - 1] != INF):
sp[i][j][e] = min(sp[i][j][e], graph[i][a] +
sp[a][j][e - 1])
return sp[u][v][k]
# Driver Code
# Define number of vertices in
# the graph and infinite value
V = 4
INF = 999999999999
# Let us create the graph shown
# in above diagram
graph = [[0, 10, 3, 2],
[INF, 0, INF, 7],
[INF, INF, 0, 6],
[INF, INF, INF, 0]]
u = 0
v = 3
k = 2
print("Weight of the shortest path is",
shortestPath(graph, u, v, k))
# This code is contributed by PranchalK
C#
// Dynamic Programming based C# program to find
// shortest path with exactly k edges
using System;
class GFG
{
// Define number of vertices in the graph
// and infinite value
static readonly int V = 4;
static readonly int INF = int.MaxValue;
// A Dynamic programming based function to
// find the shortest path from u to v
// with exactly k edges.
int shortestPath(int [,]graph, int u, int v, int k)
{
// Table to be filled up using DP. The value
// sp[i][j][e] will store weight of the shortest
// path from i to j with exactly k edges
int [,,]sp = new int[V, V, k + 1];
// Loop for number of edges from 0 to k
for (int e = 0; e <= k; e++)
{
for (int i = 0; i < V; i++) // for source
{
for (int j = 0; j < V; j++) // for destination
{
// initialize value
sp[i, j, e] = INF;
// from base cases
if (e == 0 && i == j)
sp[i, j, e] = 0;
if (e == 1 && graph[i, j] != INF)
sp[i, j, e] = graph[i, j];
// go to adjacent only when number of
// edges is more than 1
if (e > 1)
{
for (int a = 0; a < V; a++)
{
// There should be an edge from i to a and
// a should not be same as either i or j
if (graph[i, a] != INF && i != a &&
j!= a && sp[a, j, e - 1] != INF)
sp[i, j, e] = Math.Min(sp[i, j, e],
graph[i, a] + sp[a, j, e - 1]);
}
}
}
}
}
return sp[u, v, k];
}
// Driver Code
public static void Main(String[] args)
{
/* Let us create the graph shown in above diagram*/
int [,]graph = new int[,]{ {0, 10, 3, 2},
{INF, 0, INF, 7},
{INF, INF, 0, 6},
{INF, INF, INF, 0} };
GFG t = new GFG();
int u = 0, v = 3, k = 2;
Console.WriteLine("Weight of the shortest path is "+
t.shortestPath(graph, u, v, k));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Dynamic Programming based Javascript program to find shortest path with
// exactly k edges
// Define number of vertices in the graph and infinite value
let V = 4;
let INF = Number.MAX_VALUE;
// A Dynamic programming based function to find the shortest path
// from u to v with exactly k edges.
function shortestPath(graph, u, v, k)
{
// Table to be filled up using DP. The value sp[i][j][e] will
// store weight of the shortest path from i to j with exactly
// k edges
let sp = new Array(V);
for(let i = 0; i < V; i++)
{
sp[i] = new Array(V);
for(let j = 0; j < V; j++)
{
sp[i][j] = new Array(k + 1);
for(let l = 0; l < (k + 1); l++)
{
sp[i][j][l] = 0;
}
}
}
// Loop for number of edges from 0 to k
for (let e = 0; e <= k; e++)
{
for (let i = 0; i < V; i++) // for source
{
for (let j = 0; j < V; j++) // for destination
{
// initialize value
sp[i][j][e] = INF;
// from base cases
if (e == 0 && i == j)
sp[i][j][e] = 0;
if (e == 1 && graph[i][j] != INF)
sp[i][j][e] = graph[i][j];
// go to adjacent only when number of edges is
// more than 1
if (e > 1)
{
for (let a = 0; a < V; a++)
{
// There should be an edge from i to a and
// a should not be same as either i or j
if (graph[i][a] != INF && i != a &&
j!= a && sp[a][j][e-1] != INF)
sp[i][j][e] = Math.min(sp[i][j][e],
graph[i][a] + sp[a][j][e-1]);
}
}
}
}
}
return sp[u][v][k];
}
let graph = [[0, 10, 3, 2], [INF, 0, INF, 7], [INF, INF, 0, 6], [INF, INF, INF, 0]];
let u = 0, v = 3, k = 2;
document.write("Weight of the shortest path is "+
shortestPath(graph, u, v, k));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
9
La complejidad temporal de la solución anterior basada en DP es O(V 3 K) , que es mucho mejor que la solución ingenua.
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