경로를 따라 최소 에지 가중치

Question

임의의 꼭지점 사이의 모든 경로를 따라 최소 에지 가중치 집합의 최대 값을 찾는 방법은 무엇입니까? (u,v)?

나는 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 

최소 에지 무게는 따라서 결과는 max(1, 3) = 3

Answer 1

예, 플로이드 - Warshall의 수정 작업 것입니다 3

입니다 - 대신 최단 경로 길이는 최대 경로 "너비"를 추적합니다.

두 개의 꼭지점에만 관심이있는 경우 빈 그래프로 시작하고 가중치로 정렬 한 가장자리를 추가합니다 (높음에서 낮음). 해당 노드가 연결되면 마지막 가장자리가 추가되어 최대 "너비"가 제공됩니다. 제대로 처리했는지 (즉, 연결이 끊어져 있는지 확인하기 위해 분리 세트를 사용) Floyd-Warshall보다 빠릅니다.

참고 : 긍정적 인 가중치 만 고려합니다.