경로를 따라 최소 가장자리 무게

Question

임의의 정점 사이의 모든 보유 경로를 따라 최소한의 최첨단 가중치의 최대 값을 어떻게 찾을 수 있습니까?

floyd-warshall의 수정을 생각하고 있었습니까?

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 입니다.

결과는 (u,v) 입니다.

Answer 1

예, Floyd-Warshall의 수정이 최단 경로 길이 대신 최대 경로 "너비"를 추적합니다.

두 개의 정점에만 관심이있는 경우, 더 간단한 접근 방식을 취할 수 있습니다. 빈 그래프로 시작하고 무게로 정렬 된 가장자리를 추가하십시오 (높음에서 낮음까지).문제의 노드가 연결되면 마지막 가장자리가 추가되어 최대 "너비"를 제공합니다.적절하게 완료 (즉, 연결 상태를 확인하기 위해 Disjoint 세트를 사용하여), 이것은 Floyd-Warshall을보다 빠르게 할 것입니다.

참고 : 나는 긍정적 인 가중치를 고려하고 있습니다.