python-在有向图和加权图中具有恰好k个边的最短路径生成(编辑：每个节点仅访问一次)

概述以下代码来自https://www.geeksforgeeks.org/shortest-path-exactly-k-edges-directed-weighted-graph/.所有功劳归于PranchalK.我正在处理生成k边最短路径的问题.以下代码给出了带有预定义k的最短“距离”.但是,我需要“路径”对于下面的代码,路径似乎是：0-> 2-> 3.编

以下代码来自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,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,INF,7],6],0]]     u = 0    v = 3    k = 2    print("Weight of the shortest path is",shortestPath(graph,k)) # This code is contributed by PranchalK 

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

0是开始节点,3是结束节点.边的数量是2.路径是0->. 2-> 3

编辑：阿杰的答案非常非常接近.但是,每个节点仅需要访问一次.对不起,我本来没有提到这一点.这是要测试的更大数据.

    graph = [[0,4,1],[1,7,[2,8,6,[4,1,[3,[7,3]] Weight of the shortest path is 14Shortest path is  [0,3]

最佳答案存储产生最小值的节点.每个边缘长度的重量总和< k.

def shortestPath(graph,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,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 Codeif __name__ == '__main__':    INF = 999999999999    # Let us create the graph shown    # in above diagram    graph = [[0,0]]    u = 0    v = 3    k = 2    weight,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) 

总结

以上是内存溢出为你收集整理的python-在有向图和加权图中具有恰好k个边的最短路径生成(编辑：每个节点仅访问一次) 全部内容，希望文章能够帮你解决python-在有向图和加权图中具有恰好k个边的最短路径生成(编辑：每个节点仅访问一次) 所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。