그래프에서 2 노드 사이의 다중 가중치가 최소가되는 것이 최적입니까?

Question

가중 그래프에서 최단 경로가 계산되도록 요청 된 경우 두 노드에 서로 다른 가중치를 갖는 여러 가장자리가있을 수 있습니다. 다수의 가장자리가 두 노드 사이가 경우, 우리는 최소 가중 가장자리와 방치 다른 사람을 수행 할 수 있습니다 플로이드 - 워셜 알고리즘 또는 익스트라의 알고리즘을 적용에

---

?

그렇다면 누구나 증명할 수 있습니까? 미리 감사드립니다.

Answer 1

예, 최소한 걸릴 수 있습니다. 당신이 최소한의 엣지를 가지지 않고 루트를 발견했다고 상상해보십시오. 이제 더 짧은 엣지로 대체한다면, 새로운 루트는 더 짧아 질 것입니다.

Answer 2

글쎄요. 모든 가중치가 동일한 기준을 나타 냅니까? 예) 자율 차량의 최단 경로 계획 문제를 고려하십시오. 도로 안전 요소의

품질 [사고의 역사는 그 길에서 일어난 중간 점 사이에 대상에게 통행료의

수에 도달하는 데 걸리는

• 시간처럼 돌봐 하나 개 이상의 기준이있을 수 있습니다 ]

따라서 문제는 진술에 달려 있습니다.