给定一个图，return从头到尾最多有k条边的最短路径

Question

给定一个有向图，return从顶点开始到结束最多有 k 条边的最短路径

我的尝试

from heapq import heappush, heappop
def atMostK(n, edges, start, end, k):
    """
    :type edges: List[List[int]]
    :type start: int
    :type end: int
    :type k: int
    :rtype: int
    """
    graph = {}
    for (x, y, z) in edges:
        graph[x] = graph.get(x, []) + [(y, z)]
        
    table = {}
    for v in range(n):
        table[v] = (float("inf"), 0)  
    table[start] = (0, 0)
    
    
    stack = [(0,start)]
    visited = set()
    
    while(stack != []):
        node = heappop(stack)[1]
        w, cur_k = table[node]

        if(node in visited):
            continue
            
        visited.add(node)
        if(node in graph):
            for (v, weight) in graph[node]:
                
                
                cur_weight, amount = table[v]
                
                if(cur_weight > weight + w):
                    table[v] = (weight + w, amount + 1)
                    heappush(stack, (weight + w, v))
                    
    if(table[end][0] == float("inf")):
        return -1
    
    return table[end][0]
    

# fails on this

n = 3
edges = [[0,1,100],[1,2,100],[0,2,500]]
start = 0
end = 2
k = 1

print(atMostK(n, edges, start, end, k)) # 200, incorect result. Should be 500

# passes on this

n = 3
edges = [[0,1,100],[1,2,100],[0,2,500]]
start = 0
end = 2
k = 2

print(atMostK(n, edges, start, end, k)) # correct result

我尝试使用 dijkstra 算法，但是当我由于超过 k 边要求而需要回溯到之前访问过的节点时，我运行遇到了麻烦。

因此，例如从开始 = 0、结束 = 2 和 k = 1 使用此图

它将首先访问 0，然后转到 0->1 边缘，因为它比 0->2 边缘便宜，但为了转到 2，我需要另一个边缘，但我只允许 k=1，所以正确的结果应该是 500.

它适用于不需要我回溯到已经访问过的节点的图表，但除此之外它不会工作。我该怎么做？

Answer 1

使用 Bellman-Ford 的轻微修改，在最坏的情况下，您可以在 O(K*(|V| + |E|)) 时间内解决这个问题，对于一般情况有许多可能的优化。

运行具有 k 次迭代的外循环；在 ith 迭代中，我们正在计算来自 start 的最小权重路径，最多有 i 条边。您确实需要从通常的 Bellman-Ford 进行一些额外的复制，以确保更新仅基于先前的循环迭代。

def atMostK(n, edges, start, end, k):
    """
    :type edges: List[List[int]]
    :type start: int
    :type end: int
    :type k: int
    :rtype: int
    """

    table = {}
    for v in range(n):
        table[v] = (float("inf"), 0)
    table[start] = (0, 0)

    for _ in range(min(k, n-1)):
        new_table = table.copy()
        for u, v, weight in edges:
            if table[u][0] + weight < new_table[v][0]:
                new_table[v] = (table[u][0] + weight, u)
        table = new_table

    if table[end][0] == float("inf"):
        return -1

    return table[end][0]

您也可以修改 Dijkstra 来执行此操作，但时间复杂度（和性能）可能更差且更难分析。您的最低优先级队列可以根据 (weight, num_edges, vertex) 进行排序，并进行检查以确保 num_edges 低于 k。

给定一个图，return从头到尾最多有k条边的最短路径

Given a graph, return the shortest path from start to end that has at most k edges

python

graph

dijkstra