python - 在有向加权图中恰好有 k 条边的最短路径生成(编辑 : visit each node only once)

Question

以下代码来自https://www.geeksforgeeks.org/shortest-path-exactly-k-edges-directed-weighted-graph/ .所有功劳归功于 PranchalK。

我正在处理生成 k 边最短路径的问题。下面的代码给出了具有预定义 k 的最短“距离”。
但是，我需要“路径” 对于下面的代码，路径似乎是:
0 --> 2 --> 3 .
编辑:Ajay 的代码解决了这个问题。但是，每个节点只需要访问一次。我没有在原始问题中提到这一点。我已经包含了一个额外的数据集来测试它。

# 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 

预期结果是:
[0,2,3]

0为起始节点，3为结束节点。边数为2，路径为0 --> 2 --> 3

编辑:Ajay 的回答非常非常接近。但是，每个节点只需要访问一次。很抱歉，我最初没有提到这一点。这是一个更大的数据来测试。

    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

存储产生最小值的节点。每条边长 < 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)