그래프 최소 무게 경로

Question

나는 가중 그래프를 가지고 있습니다. 노드 S에서 노드 E까지의 최적 경로를 찾고 싶으므로 그 경로 내에있는 최대 단일 에지 가중치가 가능한 한 작습니다. 예를 들어

:

이 그래프에 대한

S -> E (w=40) 
S -> A (w=30) 
A -> E (w=20) 

이 djikstra이> 비용 (40)와 E S-을 할 최단 경로를 계산하는 것은 내가 대신 원하는 비용 (S-> A-> E입니다 max (30, 20) = 30).

dijkstra를 이와 같은 방법으로 수정할 수 있습니까? 또는 이것을 수행하는 알려진 알고리즘이 있습니까?

Answer 1

이 문제를 해결할 방법은 우선 순위 대기열/힙에서 거리 (비교 값)를 저장하는 방식을 변경하는 것이지만 그렇지 않은 경우 구조는 Dijkstra 's와 유사하게 유지됩니다. 전체 거리가 아닌 구성된 경로에서 최대 가중치를 지금까지 저장합니다. 이렇게하면 우선 순위 대기열에서 가장 작은 것부터 순서대로 진행합니다.

그래서 당신이 준 예제에서, 그것은 30의 aw, 다른 하나는 40 인 반면 S -> A로 시작할 것입니다. 두 번째 실행에서 그것은 w = 20으로 갈 것이고 A -> E는 Math.max (20, 30)가 < 40이기 때문에 우선 순위 큐/힙에 먼저 저장됩니다.

목적지에 도착하면 경로가 가장 작게 보장됩니다. 희망이 이해가!

1) 모든 가장자리를 제거하고 일종의 첫번째 분으로 가장자리 :

Answer 2

당신은 욕심쟁이 알고리즘 변형을 사용할 수 있습니다.

2) 원본 노드에서 대상 노드까지의 경로가있을 때까지 그래프의 가장자리를 최소에서 최대 순으로 추가하십시오. 그 길은 당신이 찾고있는 길입니다.