Как изменить 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

Итак, это dijkstra, который я сейчас кодировал с Python, но я не не знаю, как мне изменить это, чтобы рассчитать маршрут с наименьшим возможным максимальным весом

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 = 1, T = 5

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

Answer 2

Я не могу определить максимальный путь узкого места. Я предполагаю, что это путь от S до T, и минимальный край на нем максимален. если это так, я не думаю, что мы можем установить очередь, сохраняя монтоничность (я чувствую, что это природа дижи). может быть, вы можете использовать бинарный поиск только с BFS?