时间戳

首页 > 解决方案 > 给定边的最短路径

algorithm - 给定边的最短路径

问题描述

我想使用k边缘从源（u）中找到最短路径。此解决方案似乎有效，但它搜索具有k给定节点边缘的路径v。如果k边缘在到达之前被覆盖v怎么办？我只想要从u覆盖k边缘覆盖的所有路径中的最短路径。v不需要到达。

来自上述链接的代码：

# 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, 4, 2, 6, 5], 
            [INF, 0, 4, 2, 5], 
            [INF, INF, 0, 4, 3], 
            [INF, INF, INF, 0, 3],
            [INF, INF, INF, INF, 0]] 
    u = 0
    v = 4
    k = 3
    print("Weight of the shortest path is", 
            shortestPath(graph, u, v, k))

标签： algorithmdata-structuresshortest-path

解决方案

您可能可以修复该代码（通过根本不传递或查看v- 见下文）。但我建议简单地修改 Dijkstra 的算法，最多从起始节点探索 3 条边。Dijkstra 从一开始就找到所有最短长度的路径。只需在路径到达第三条边时停止它（这将要求您在距离之外保持边数）。

修改上面的代码也可以，但肯定会更慢，因为除非图形是树，否则您将多次查看每条边。

INF = 999999999999
def nearest_in_k_steps(graph, u, k): 
    print(f"Entering {u}, {k} steps remaining")
    V = len(graph)
   
    # Base case
    if k == 0: 
        return 0, u

    # Initialize result 
    best_dist = INF 
    best_target = None

    # Go to all adjacents of u and recurse 
    for i in range(V): 
        if graph[u][i] != INF and u != i: 
            candidate_dist, candidate_target = nearest_in_k_steps(graph, i, k - 1) 
            candidate_dist += graph[u][i]
            if candidate_dist < best_dist:
                print(f"Hmm, path via {i} (d={candidate_dist}) is better than via {best_target} (d={best_dist})")
                best_dist = candidate_dist
                best_target = candidate_target

    print(f"Returning from {u}, {k} steps remaining: d={best_dist} to {best_target}")
    return best_dist, best_target

# Driver Code 
if __name__ == '__main__': 
    # Let us create the graph shown 
    # in above diagram 
    graph = [[0,    4,   2,   6,   5], 
            [INF,   0,   4,   2,   5], 
            [INF, INF,   0,   4,   3], 
            [INF, INF, INF,   0,   3],
            [INF, INF, INF, INF,   0]] 
    start = 0
    steps = 3
    nearest_dist, nearest_target = nearest_in_k_steps(graph, start, steps)
    print(f"Node {nearest_target} is the nearest {steps}-step neighbor of {start}: distance = {nearest_dist}")

请注意，有几个打印件只是为了帮助您了解代码的工作原理。

推荐阅读