Dijkstra 대신 Prim의 알고리즘을 사용하여 최단 경로를 찾을 수 있습니까?

Question

나는 Dijkstra의 알고리즘을 이해하고 중요한 결과없이 구현하는 데 하루 종일 싸우고 있습니다. 나는 도시와 거리의 행렬을 가지고있다. 제가하고 싶은 것은 출발점과 목적지 지점을 부여하여 도시 간 최단 경로를 찾는 것입니다.

예 :

 __0__ __1__ __2__ 
0 | 0 | 34 | 0 | 
    |-----|-----|-----| 
1 | 34 | 0 | 23 | 
    |-----|-----|-----| 
2 | 0 | 23 | 0 | 
    ----- ----- ----- 

나는이 문제를 해결하기위한 다른 방법이 있는지 궁금 시작했다. 원점에서 Prim의 알고리즘을 적용한 다음 대상 점을 찾을 때까지 전체 트리를 반복합니다.

Answer 1

Prim의 알고리즘을 적용한 다음 결과 트리를 걸을 수도 있지만 잘못했을 수 있습니다. 각 모서리의 무게가 같은 그래프를 가지고 있다고 가정하십시오. Prim의 알고리즘은 트리에 추가 할 수있는 가장자리 집합에서 최소 가중치 가장자리를 선택하기 만합니다. 두 노드 사이의 최단 경로로 이어질 에지를 선택하지 않을 수도 있습니다. 가정 :

 __0__ __1__ __2__ 
0 | 0 | 1 | 1 | 
    |-----|-----|-----| 
1 | 1 | 0 | 1 | 
    |-----|-----|-----| 
2 | 1 | 1 | 0 | 
    ----- ----- ----- 

은 프림의를 통해, 노드 0 당신이 할 수에서 시작하여 트리를 만들기 위해 가장자리 0-1과 0-2를 선택합니다. 또는, 가장자리를 0-1 및 1-2로 선택하여 나무를 만들 수 있습니다. 첫 번째 모서리 집합에서 0부터 2까지의 최소 길이 경로를 찾을 수 있지만 두 번째 모서리 집합에서는 최소 경로를 찾지 못합니다. Prim 알고리즘에서 추가되는 에지를 선험적으로 결정할 수 없기 때문에이를 사용하여 최단 경로를 찾을 수 없습니다.

당신은 Bellman-Ford 알고리즘을 고려해 볼 수 있습니다.하지만 네거티브 에지 가중치를 다루지 않으면 Dijkstra의 알고리즘이 더 좋습니다.