Shortest path GENERATION with exactly k edges in a directed and weighted graph (edit: visit each node only once)

Question

This following code is from https://www.geeksforgeeks.org/shortest-path-exactly-k-edges-directed-weighted-graph/. All credit goes to PranchalK.

I am dealing with the problem of generating k-edge shortest path. The code below gives the shortest "distance" with pre-defined k.
However, I will need the "path" For the code below the path seems to be:
0 --> 2 --> 3 .
Edit: Ajay's code solves this problem. However, each node needs to be visited only once. I haven't mentioned this in the original question. I have included an extra data set to test it.

# Python3 program to find shortest path 
# with exactly k edges 

# Define number of vertices in the graph 
# and inifinite 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 

Expected outcome is:
[0,2,3]

0 is the starting node, 3 is the ending node. The number of edges is 2. The path is 0 --> 2 --> 3

Edit: Ajay's answer is very very close. However, each node needs to be visited only once. I am sorry that I haven't mentioned this originally. Here is a bigger data to test.

    graph = [[0, 10, 3, 2,4,1],
            [1, 0, 3, 7,4,1],
            [2, 8, 0, 6,0,1],
            [4, 1, 3, 0,1,2],
            [3, 1, 2, 2,4,1],
            [7, 1, 3, 0,3,3]] 

Weight of the shortest path is 14
Shortest path is  [0, 2, 0, 2, 3]

Answer 1

By checking the existing NetworkX algorithms in Shortest Paths it seems none of these allows to directly obtain all simple paths between two nodes and along with the corresponding weights.

So it will be necessary to do both things separately:

• Compute all paths between two given nodes, and keep only those of length k
• And then compute the weight of each of these indivudual paths and select the one of less weight

---

General Solution

def shortest_path_k_edges(graph, source, target, k):
    '''
    Computes the shortest simple path with
    exactly k edges of a weighted graph 
    between the specified source and target
    ----
    graph: np.array
       Adjacency matrix for the graph
    source: int
       Source node
    target: int
       Target node
    k: int
       Amount of edges of the path
    ----       
    Returns:
       Shortest k length path    
    '''
    import networkx as nx
    # Builds graph from the adjacency matrix
    g = nx.from_numpy_array(graph)
    # Generates all simple paths (no repeated nodes) 
    # in the graph from source to target
    all_paths = nx.all_simple_paths(g, source, target)
    # Keeps only paths with k edges
    paths = [i for i in all_paths if len(i) == k+1]
    # Compute the weights of each of the paths
    # using the adjacency matrix
    weights = [sum(graph[i[j], i[j+1]] 
                   for j in range(len(i)-1)) 
               for i in paths]
    # Return path of minimum weight, and
    # corresponding weight
    min_w = min(weights)
    return paths[weights.index(min_w)], min_w

---

Output

Lets check the results with the proposed parameters:

u = 0
v = 3
k = 2
INF = 999999999999
import numpy as np
graph = np.array(
       [[0, 10, 3, 2], 
        [INF, 0, INF, 7], 
        [INF, INF, 0, 6], 
        [INF, INF, INF, 0]])

path, weight = shortest_path_k_edges(graph, u, v, k)

print(path)
# [0, 2, 3]

print(weight)
# 9

Answer 2

Store the node which yields min. sum of weight for every edge length < k.

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
    k_minus_one_path = []
    least_sum_node = None
    for i in range(V):
        if graph[u][i] != INF and u != i and v != i:
            rec_res, path = shortestPath(graph, i, v, k - 1)
            if rec_res != INF:
                if res > graph[u][i] + rec_res:
                    k_minus_one_path = path
                    least_sum_node = i
                    res = graph[u][i] + rec_res

    if least_sum_node is not None:
        k_minus_one_path.insert(0, least_sum_node)

    k_path = k_minus_one_path

    return res,k_path

# 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
    weight, path = shortestPath(graph, u, v, k)
    if weight != INF:
        path.insert(0, u)  # source
        path.append(v)  # Destination
    print("Weight of the shortest path is", weight)
    print("Shortest path is ", path)