Минимальный вес ребра вдоль пути

Question

Как мне найти максимум набора минимальных весов ребер на всем возможном пути между произвольными вершинами? (u,v)?

Я имел в виду модификацию Флойда-Уоршалла?

i.e. Path 1: s - a - b - c - d - t with weights 1 - 5 - 6 - 10 - 9

Минимальный вес ребра – 1.

Path 2: s - x - y - z - w - t with weights 3 - 9 - 8 - 6 - 7

Минимальный вес ребра 3.

Таким образом, результат max(1, 3) = 3

Answer 1

Да, модификация Флойда-Уоршалла будет работать - вместо длины кратчайшего пути вы будете отслеживать максимальную «ширину» пути.

Если вас интересуют только две вершины, вы можете использовать более простой подход:начните с пустого графа и добавьте ребра, упорядоченные по их весу (от большего к меньшему).Когда рассматриваемые узлы соединяются, последнее добавленное ребро дает максимальную «ширину».Сделано правильно (т.используя непересекающийся набор для проверки связности), это будет быстрее, чем Floyd-Warshall.

Примечание:Я рассматриваю только положительные веса.