График минимального веса пути
У меня есть взвешенный график. Я хочу найти лучший путь от узла S к узлу E, чтобы максимальный вес одного ребра, который был внутри этого пути, был наименьшим из возможных.
Например:
S -> E (w=40)
S -> A (w=30)
A -> E (w=20)
Для этого графа djikstra вычислил бы самый короткий путь, чтобы быть S->E со стоимостью 40. Вместо этого я хочу S->A->E (с ценой max(30, 20) = 30).
Можно ли таким образом модифицировать дейкстру? Или есть какой-нибудь известный алгоритм, который выполняет это?
2 ответа
Способ решения этой проблемы - это изменение способа хранения расстояния (сравнительного значения) от приоритетной очереди / кучи, но в противном случае структура останется похожей на структуру Дейкстры. Пока вы сохраняете максимальный вес в построенной траектории вместо общего расстояния. Таким образом, в вашей очереди приоритетов вы будете идти в первую очередь для самых маленьких.
Таким образом, в приведенном вами примере он будет начинаться с S -> A, потому что у него значение aw равно 30, а у другого - 40. Во втором исполнении оно будет равно w = 20, а A -> E, потому что Math.max(20, 30) < 40, поэтому он будет сохранен ранее в приоритетной очереди / куче.
Как только вы доберетесь до места назначения, этот путь будет гарантированно наименьшим. Надеюсь, что это имеет смысл!
Вы можете использовать вариант Greedy Algorithm:
1) Удалите все ребра и сначала отсортируйте ребра с помощью min.
2) Добавляйте ребра к графику в порядке от минимального до максимального, пока не появится путь от исходного узла к целевому узлу. Этот путь - это путь, который вы ищете.