위의 다양한 대답은 수정 된 가중치 함수를 사용한 Dijkstra 알고리즘을 간단히 제안합니다. 예를 들어 w(e) = -c(e) 또는 'w (e) = 1/c (e)'입니다. 여기서 w(e)은 알고리즘에서 사용하는 가장자리의 가중치이고 c(e)은 원래 문제 공식에서 가장자리의 용량입니다.
다음은 작동하지 않습니다.
부정확 한 결과를 초래할 수있는 반례를 쉽게 만들 수 있습니다. 예를 들어, 그래프 고려해
a---3-->b---3--->c---3-->d
\ ^
\ |
\----------3----------|
가
a의 값을 가정한다 ('알고리즘 제제 노드
a의 거리)는 0이다.
a에서
d까지의 두 경로는이 문제에서 동일합니다. 그러나 짧은 경로를 사용하는 동안 가장자리 용량을 무시하면 distance (d)는 긴 경로를 사용하여
(-3)+(-3)+(-3) = -9이며
-3이됩니다. 가장자리 용량을 역산하면 긴 경로를 사용하는 거리 (d)는
(1/3)+(1/3)+(1/3)=1이되고 짧은 값은
(1/3)이됩니다.
무엇 작업 알고리즘의 완화 공정을 변경, 즉 대신 첨가 (+가)의 기능을 이용하여 각각 사용하는 함수 (<) 덜보다 것이다 min 및보다 큰 (>)을하고 min-heap 대신 max-heap을 사용하십시오. 모서리 가중치를 무효화하고 덜 사용하는 경우 마지막 두 개를 피할 수 있습니다. + 연산자가 필요하기 때문에 @이 필요합니다. 값은 이고 +은 a=0 만 사용할 수 있습니다.
키스 랜달 (Keith Randall)이 처음으로 제시 한 정답입니다.
수정 된 알고리즘이 올바른지 공식적으로 증명하는 것이 좋습니다. 입증해야 할 내용은 다음과 같습니다. - u이 루프 반복에서 최대 값이 d(u) 인 노드 인 경우 표시되지 않은 노드가 포함 된 경로는 보다 큰 거리를 u에 생성 할 수 없습니다.
표시되지 않은 노드는 다른 모든 노드가 'u'거리보다 작거나 같기 때문에 직관적으로 볼 수 있습니다 (최대 거리가있는 노드로 u을 선택했기 때문에). 그리고 생성 된 거리 경로는 min의 연속적인 호출에 의해 생성되므로 더 작지 만 커질 수는 없습니다.
"... A에서 B까지.이 경로에서 가장 작은 가장자리 인 int를 반환하지만 A에서 B로가는 다른 경로와 비교할 때 가장 큰 가장자리" 뭐 ? 당신은 "A에서 B로 가장 작지만 A에서 B로 가장 큰 것"이라고 말합니다. –
A에서 B까지 더 많은 경로가있을 수 있습니다. 가장 큰 트럭을 A에서 B로 운전하고 싶습니다.선택한 모서리는 선택한 경로의 가장 작은 모서리이지만 A에서 B까지가는 다른 루트의 가장 작은 모서리와 비교할 때 가장 큰 것입니다. – Algific