Каков алгоритм, который находит минимальную наибольшую стоимость всех ребер?

Question

Я пытаюсь решить проблему, когда мне нужно найти минимальную цену за шаг, чтобы добраться от начального до целевого узла. Я думаю, что этот алгоритм существует, но я не могу найти название этого алгоритма. В случае, когда я работаю, есть только положительные края и могут быть циклы. Это не dijkstra, потому что я ищу не общую минимальную стоимость, а стоимость, которая представляет минимальную наивысшую стоимость всех шагов.

В следующем примере этот алгоритм, таким образом, выведет 3 как 3самая высокая минимальная стоимость, для которой алгоритм может найти путь. И, таким образом, это не минимальная стоимость, так как это будет 4.

* Начальный узел серый, а целевой узел зеленый.

Я думаю,такой алгоритм существует, я попытался выполнить поиск в Google, но пока не смог найти название этого алгоритма.

Answer 1

Это можно решить с помощью простой модификации на dijkstra.

Dijkstra работает, всегда выбирая путь минимальной стоимости. Мы знаем, что до тех пор, пока затраты на пути никогда не уменьшаются при перемещении по графику (это верно в вашем случае), мы всегда найдем оптимальный ответ, выполняя итерацию в порядке от самой низкой до самой высокой стоимости пути. Нам просто нужно изменить функцию cost, чтобы она была максимальной для каждого пути, и запустить dijkstra.

Вот реализация псевдокода (в основном, python):

import priority_queue

def min_cost_path(start, end):
    min_heap = priority_queue([[0, start]]) # queue in form of (cost, node)
    visited = set()

    while min_heap:
        # get lowest weight path thus far
        # cost is the lowest cost possible to get to node
        cost, node = min_heap.pop()
        # optimal path to this node has already been found, ignore this
        if node in visited: continue
        if node == end: return cost
        # this node has been visited
        visited.add(node)
        # add candidate node-weights to the queue
        for weight, neighbor in neighbors(node):
            if neighbor not in visited:
                min_heap.push((max(weight, cost), neighbor))

    return -1 # not possible

Answer 2

Ну, я только слышал о такой проблеме для неориентированных графов, для ориентированных (как ваш пример), я не знаю, как она называется, но не сложно придумать какой-нибудь эффективный способ ее решения:

1. Мы можем просто найти ответ в двоичном виде, начальное пространство поиска равно [0, maxWeightInWholeGraph]

2. Во время каждой итерации двоичного поиска мы выбираем какое-то среднее значениеm и нам нужно проверить, существует ли путь от начального узла к целевому узлу с весом ребер <= m

3. Это можно сделать с помощью простой BFS, обходя только разрешенные ребра

4. Теперь мы разделим наше пространство поиска пополам, выбрав левую часть, если мы нашли путь к начальной цели, и правую часть в противном случае.

5. продолжим бинарный поискпока мы не дойдем до ответа

Сложность этого подхода: O ((| V | + | E |) * log2 (maxWeightInWholeGraph))