주어진 최단 경로로부터 대응하는 그래프 찾기

Question

n 포인트 n 포인트와 이들 포인트 사이의 거리 d를 감안할 때, 나는 이러한 거리를 초래할 무 방향성 가중 그래프를 찾아야합니다. Prim의 알고리즘을 사용하여 MST를 찾으려고 시도했지만,이 세트는 크기가 n-1이고 n 개의 필요한 모서리를 포함하지 않습니다. 예 : N 거리 나 해당 가장자리를 찾을 필요가

0 3 5 
3 0 4 
5 4 0 

에 의해 N 제공 :

그래프 결과

1 - 2 = 3 
1 - 3 = 5 
2 - 3 = 4 

:

 3 
1 --------- 2 
\  /
    \5  /4 
    \ /
    \ /
     3 

그러나 프림의이 이후 첫 번째 두 가장자리를 반환 MST에는 사이클이 없습니다.

Answer 1

이러한 거리를 발생시키는 그래프는 모든 노드에서 다른 모든 노드까지의 가장자리가있는 그래프이며 해당 가장자리의 길이는 행렬에 따른 거리입니다. (나는 당신이주는 예제가 방향이없는 것처럼 보이고 여기서는 가중치와 길이의 차이점이 무엇인지 모르기 때문에 당신이 unweighted 지시어로 무엇을 의미하는지 확신 할 수 없다.)

또 다른 옵션은 Prim의 알고리즘을 사용한 것처럼 거리가 증가하는 순서를 고려하는 것입니다. 또한 가장자리가 두 끝을 연결해야하는지 확인하는 것 외에 최소 거리 지금까지 재구성 된 그래프의 끝점 사이의 거리는 행렬의 거리와 같습니다. 그렇지 않은 경우 끝까지 그래프에 연결되어 있어도 가장자리를 추가하십시오.