두 개의 정점 사이의 경로 비용이 최대 비용 비용이되도록 최단 경로 문제를 수정하면 모든 쌍의 정점 u와 v, 최소 비용 스패닝 트리를 따르는 경로 사이의 경로는 최소 비용 경로입니다.최소 비용 경로를 얻기위한 최단 경로 수정
이 접근 방식이 맞는지 어떻게 증명할 수 있습니까? 그것은 의미가 있지만 확실하지 않습니다. 누구든지이 알고리즘이 문학에 있는지 알고 있습니까? 거기에 이름이 있니?
MST의 몇 가지 기본 사실을 사용할 수 있습니다 (보통 Prim의 & Kruskal의 알고리즘에 대한 정확성 증명에서 논의 됨). 지금 중요한 하나는 그
LEMA 1
는그래프 절단 (두 개별 세트로 정점 분할) 될 것이다 두 부분을 연결하는 MST의 가장자리 주어 두 부분을 연결하는 가장 싼 가장자리.
우리는 지금 MST의 경로를 증명할 수있는 모든 분에서 선정 된 경로 (증거는 저렴 가장자리이 있다면 우리가 쉽게 저렴 스패닝 트리를 contruct 할 수있을 것입니다, straighfoward됩니다) 당신은 최대-비용을 고려하는 경우 :
은 임의의 두 정점 s 및 G에서 t 지금 uv이 경로에서 가장 비싼 가장자리하자 G.의 MST에서 그들을 연결하는 경로 p을 가져 가라. 이 엣지 위로 잘라낸 그래프를 기술 할 수 있습니다. 하나의 파티션은 정점이 MST의 u쪽에 있고 다른 파티션은 정점이 v면에 있습니다. s과 t을 연결하는 모든 경로는이 절단을 통과해야하므로 모든 경로의 비용은 s에서 t까지 적어도이 절단에서 가장 저렴한 에지의 비용이어야한다고 판단 할 수 있습니다. 그러나 Lemma 1은 uv가이 커팅에서 가장 싼 에지라고 알려주기 때문에 p은 최소 비용 경로 여야합니다.
항상 최소 스패닝 트리가 있습니다 (제한된 수의 트리가 있습니다 - 서브 세트는 최소이어야 함) 모든 스패닝 트리의 모든 두 노드 사이에는 항상 경로가 있습니다 (트리가 모든 꼭지점에 걸쳐 있기 때문에). 그 증명은 기본적으로 비용이 최대 값에 의해 결정되는 경우 MST의 경로가 최소 비용 경로임을 나타냅니다. – hugomg
:
의 기초 과정 Dijkstra's algorithm 비슷 Prim's algorithm에 사용 된 욕심 많은 프로세스 Prim의 목적은 그래프의 모든 노드를 연결하는 최소 스패닝 트리를 찾는 것입니다. Dijkstra는 두 노드 간의 최저 비용 경로에만 관심이 있습니다.
최단 경로 문제 *는 * 최소 비용 문제입니다. 여기서 "비용"은 거리로 정의됩니다. 거리와 다른 * 비용이있는 문제에 대해 이야기하고 있습니까? 최소화하고 싶은 비용은 무엇입니까? 교통/운전은 거리와 시간이라는 두 가지 비용이 드는 문제입니다. 짧지 만 번잡 한 거리는 거리 비용은 낮지 만 시간 비용은 높아지며 둘 중 하나 또는 다른 하나 또는 두 가지 가중치 조합을 최소화 할 수 있습니다. –