수도 코드
=> 프림 알고리즘과 유사.
- F는 공집합에서 시작.
- Y: vertex들의 집합. v1은 출발점으로 미리 넣어놔
- 반복이 n-1되는것도 프림과 똑같아
- 성능도 O(n^2)으로 똑같아.
프림과 차이점
- 프림에서는 nearest[i] 사용. => 다익은 touch[i] 사용
- 프림에서는 distance[i] 사용. => 다익은 length[i] 사용
length 값은 맨처음에는 v1에서 다이렉트 자신의 거리.
알고리즘이 진행되면서 더 좋은 값이 나오면 줄어들어.
최종적으로는 v1부터 자기자신까지의 length의 합.
초기 length
초기 touch
- V-Y 집합 애들이 Y가 되기 직전에 터치하는 애.
맨 처음에는 1번밖에 없지.
두번째
- 이제 v1에서 다이렉트로 가는 제일 짧은 정점은 정해졌어.
- 나머지애들도 근데 다이렉트 v1보다 v5거치면 더 짧아지지 않을까? > 검사!!
- ex) v2는 기존 7인데 v5 거치면 1+INF .. 아 기존이 더낫네
v4는 기존 6인데 v5거치면 1+1 = 2로 낫네. touch도 5로 변경!
시나리오 참고
- 한번 선택되어진 놈은 다시는 더 짧아지지 않아
