Shortest path with exactly k edges in a directed and weighted graph - GeeksforGeeks
Given a directed and two vertices 'u' and 'v' in it, find shortest path from 'u' to 'v' with exactly k edges on the path.
DP: The idea is to build a 3D table where first dimension is source, second dimension is destination, third dimension is number of edges from source to destination, and the value is count of walks.
O(Vk): The idea is to browse through all paths of length k from u to v using the approach discussed in theprevious post and return weight of the shortest path. A simple solution is to start from u, go to all adjacent vertices and recur for adjacent vertices with k as k-1, source as adjacent vertex and destination as v.
Using DFS:
https://github.com/dheeraj9198/Algorithms-and-Data-Structures-in-Java/blob/master/src/Graph/ShortestPathWithExactlyKEdges.java
Related: Count all possible walks from a source to a destination with exactly k edges
Read full article from Shortest path with exactly k edges in a directed and weighted graph - GeeksforGeeks
Given a directed and two vertices 'u' and 'v' in it, find shortest path from 'u' to 'v' with exactly k edges on the path.
DP: The idea is to build a 3D table where first dimension is source, second dimension is destination, third dimension is number of edges from source to destination, and the value is count of walks.
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];}O(Vk): The idea is to browse through all paths of length k from u to v using the approach discussed in theprevious post and return weight of the shortest path. A simple solution is to start from u, go to all adjacent vertices and recur for adjacent vertices with k as k-1, source as adjacent vertex and destination as v.
/ A naive recursive function to count walks from u to v with k edgesint 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;}Using DFS:
https://github.com/dheeraj9198/Algorithms-and-Data-Structures-in-Java/blob/master/src/Graph/ShortestPathWithExactlyKEdges.java
Related: Count all possible walks from a source to a destination with exactly k edges
Read full article from Shortest path with exactly k edges in a directed and weighted graph - GeeksforGeeks
