python - 如何修改 dijkstra 以计算最小最大瓶颈路线？

Question

编辑：找到解决方案，这是找到最小最大瓶颈路线的工作算法。

def dijkstra(g,s):

    for i in g.vertices:
        g.dist[i] = INF
        g.pred[i] = 0

    g.dist[s] = 0

    queue = [i for i in g.vertices]

    while len(queue) > 0:
        minval = INF
        u = 0
        for vert in queue:
            if g.dist[vert] < minval:
                minval = g.dist[vert]
                u = vert
        queue.remove(u)         

        for edge in g.adj_list[u]:
            v = edge.node
            if g.dist[v] > max(g.dist[u], edge.weight):
                g.dist[v] = max(g.dist[u], edge.weight)
                g.pred[v] = u

所以这是我现在用 Python 编码的 dijkstra，但我不知道我应该如何修改它来计算最大重量最小的路线

def dijkstra(g,s):

    for i in g.vertices:
        g.dist[i] = INF
        g.pred[i] = 0

    g.dist[s] = 0

    queue = [i for i in g.vertices]

    while len(queue) > 0:
        minval = INF
        u = 0
        for vert in queue:
            if g.dist[vert] < minval:
                minval = g.dist[vert]
                u = vert
        queue.remove(u)         

        for edge in g.adj_list[u]:
            v = edge.node
            if g.dist[v] > g.dist[u] + edge.weight:
                g.dist[v] = g.dist[u] + edge.weight
                g.pred[v] = u

Answer 1

我不能确定最大瓶颈路径，我猜它是从 S 到 T 的路径，并且它的最小边是最大的。如果是这样，我认为我们不能设置一个保持单调性的队列（我觉得这是 diji 的本质）。也许您只能将二分搜索与 bfs 一起使用？

Answer 2

如果我没记错的话，试试看，S 是 1，T 是 5

5 5
1 2 12
1 3 11
2 4 9
3 4 11
4 5 11