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

以下代码来自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 14
Shortest 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 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)

原文链接：https://www.f2er.com/python/533140.html

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

猜你在找的Python相关文章