Найти минимальные максимальные веса в взвешенном графике с помощью динамического программирования

Question

Я ищу алгоритм, который находит путь от двух вершин, скажем, 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, поэтому это предпочтительно.

Как именно решить эту проблему?

Answer 1

Вы можете использовать модифицированную версию алгоритма Флойда-Варшала , которая выполняет итерацию только для K шагов и форсирует длину пути (удаляя часть min)