以下代码来自https://www.geeksforgeeks.org/shortest-path-exactly-k-edges-directed-weighted-graph/.所有功劳归于PranchalK.
我正在处理生成k边最短路径的问题.以下代码给出了带有预定义k的最短“距离”.
但是,我需要“路径”
对于下面的代码,路径似乎是:
0-> 2-> 3.
编辑:Ajay的代码解决了此问题.但是,每个节点仅需要访问一次.我没有在原始问题中提到这一点.我包括一个额外的数据集来对其进行测试.
@H_403_12@# 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
编辑:阿杰的答案非常非常接近.但是,每个节点仅需要访问一次.对不起,我本来没有提到这一点.这是要测试的更大数据.
@H_403_12@ graph = [[0,4,1],[1,7,[2,8,6,[4,1,[3,[7,3]] Weight of the shortest path is 14 Shortest path is [0,3]
最佳答案
存储产生最小值的节点.每个边缘长度的重量总和< k.
原文链接:https://www.f2er.com/python/533140.html@H_403_12@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 Code if __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)