어느 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다.
음수 가중치를 갖는 경우에는 사용하지 못한다. 시간복잡도는 O(ElogV)이다.
0. 모든 정점까지의 최단경로를 저장할 테이블(COST_TABLE)을 만든다.
시작노드는 출발지점이니 0으로 설정하고 나머지는 매우 큰 값으로 설정한다.
1. 시작 노드를 최소힙에 집어넣는다.
{시작노드부터 해당 노드까지의 비용, 위치(인덱스나 x,y좌표)}
시작노드를 집어넣으니까 {0, 시작노드의 위치}
* 최소힙이 빌 때까지 2-4 반복
2. 최소힙에서 노드 하나(CUR)를 꺼낸다. 그러면 이 노드는 비용이 최소인 노드일 것이다.
* 노드를 집어넣으면서 간선의 비용도 같이 집어넣었다. 이것을 CUR_COST라고 하자.
CUR_COST는 시작지점부터 CUR까지 가는 비용이다. 모두 최소비용이라고 할 수는 없다.
3. 만약 COST_TABLE[CUR] < CUR_COST 라면?
이전에 이미 CUR까지 가는 더 작은 최소비용을 찾아낸 것이므로 continue 한다.
4. 꺼낸 노드(CUR)와 연결된 노드(NEXT)들을 고려한다.
후보 비용 = CUR_COST + (CUR ~ NEXT 간선의 비용) 이라 하자.
만약 (COST_TABLE[NEXT] > 후보 비용) 이라면?
-> NEXT까지 가는 더 짧은 경로를 찾은 것이므로 COST_TABLE[NEXT]을 후보비용으로 업데이트.
-> 이 경로를 활용하기 위해 최소힙에 넣는다.{후보비용, NEXT노드 위치}
어느 한 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.
시간복잡도는 O(VE)로 다익스트라에 비해 느리지만, 음의 가중치가 있는 경우에도 사용할 수 있다.
0. 모든 정점까지의 최단경로를 저장할 테이블(COST_TABLE)을 만든다.
시작노드는 출발지점이니 0으로 설정하고 나머지는 충분히 매우 큰 값으로 설정한다.
1. 아래 2번을 (정점의 개수-1)번 반복한다.
2. 모든 간선을 반복한다.
{출발지점, 도착지점, 비용} = 현재 간선
만약 (COST_TABLE[도착지점] > COST_TABLE[출발지점] + 비용) 이라면?
새로운 최단경로를 찾은 것이므로 COST_TABLE[도착지점]을 업데이트 해준다.
3. 만약 한 번 더 위 2번을 실행했는데, 새로운 최단 경로를 찾으면?
음의 사이클을 가진다는 의미이다.
위 알고리즘에서 궁금증이 생길 수 있다.
1번단계에서는 왜 (정점의 개수-1)번 반복하는거지?
시작노드 0노드에서부터 t노드까지 최단경로를 구한다고 해보자. 그러면 0노드에서부터 나머지 모든 노드를 지나쳐 t노드까지 가는 경우를 고려하는 위의 2번 단계를 수행할 것이다. 그런데 우리는 이러한 t노드를 (정점의 개수-1)개 만큼 가지고 있다. 시작노드는 이미 그 자체로 최단경로 0을 가지기 때문이다.
3번 단계가 어떻게 되는거지?
음의 사이클이 없는 경우에는 2번 단계까지 했으면 더 이상 최단경로가 없어야한다. 그런데 추가로 최단경로를 찾았다는 것은 음의 사이클이 있어서 $-\infty$로 계속 경로의 비용이 작아진다는 것을 의미한다.
크루스칼 알고리즘의 시간복잡도는 간선을 정렬하는 시간에 의해 결정된다. O(ElogE) 이다.
따라서 그래프가 간선이 비교적 적은 희소그래프(Sparse Graph**)** 일 때 사용하는 것이 좋다.