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