Найти минимальные максимальные веса в взвешенном графике с помощью динамического программирования
Я ищу алгоритм, который находит путь из двух вершин, скажем, от s до t, в графе, который имеет ровно k ребер, если пути существуют.
И если было найдено несколько путей, предпочтителен маршрут с минимальными максимальными весами одного ребра. (не общий вес).
например: скажем, K = 5
Путь 1: s - a - b - c - d - t с весами 1 - 1 - 1 - 10 - 1
максимальный вес пути 1 составляет 10
Путь 2: s - x - y - z - w - t с весами 7 - 9 - 8 - 6 - 7
максимальный вес пути 2 составляет 9, так что это предпочтительнее.
Как именно я решаю эту проблему?
1 ответ
Вы можете использовать модифицированную версию алгоритма Флойда-Варшала, которая повторяет только K шагов и форсирует длину пути (удаляя min часть)