나는 가중 그래프를 가지고 있습니다. 노드 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를 이와 같은 방법으로 수정할 수 있습니까? 또는 이것을 수행하는 알려진 알고리즘이 있습니까?
이 문제를 해결할 방법은 우선 순위 대기열/힙에서 거리 (비교 값)를 저장하는 방식을 변경하는 것이지만 그렇지 않은 경우 구조는 Dijkstra 's와 유사하게 유지됩니다. 전체 거리가 아닌 구성된 경로에서 최대 가중치를 지금까지 저장합니다. 이렇게하면 우선 순위 대기열에서 가장 작은 것부터 순서대로 진행합니다.
그래서 당신이 준 예제에서, 그것은 30의 aw, 다른 하나는 40 인 반면 S -> A로 시작할 것입니다. 두 번째 실행에서 그것은 w = 20으로 갈 것이고 A -> E는 Math.max (20, 30)가 < 40이기 때문에 우선 순위 큐/힙에 먼저 저장됩니다.
목적지에 도착하면 경로가 가장 작게 보장됩니다. 희망이 이해가!
1) 모든 가장자리를 제거하고 일종의 첫번째 분으로 가장자리 :
당신은 욕심쟁이 알고리즘 변형을 사용할 수 있습니다.
2) 원본 노드에서 대상 노드까지의 경로가있을 때까지 그래프의 가장자리를 최소에서 최대 순으로 추가하십시오. 그 길은 당신이 찾고있는 길입니다.
끝까지 여러 경로를 동시에 사용할 수있게되면 어떨까요? 나는 여전히 어느 것이 가장 좋은지 고려해야 할 것이고, 그것은 더 많은 dijkstra와 같은 해결책으로 이끌 것이다! – Lake
이것은 총 비용을 고려하지 않고 최저 비용 가장자리를 선택하는 욕심 많은 접근법을 사용하여 해결할 수 있습니다. – Wajahat