크루스칼 / 다익스트라 알고리즘

저번 포스팅에 이어서,,,

 

최소 비용 신장 트리 찾기 _ 간선 지향 전략

1. 그래프에 남아 있는 가장 가중치가 작은 간선을 선택한다.

2. 선택된 간선이 합쳐진 두 개의 정점들 사이에 있다면 그 간선을 버리고 아니면 최소 비용 신장 트리에 추가.

3. (n-1)개의 간선들이 추가될 때까지 과정 1과 2를 반복한다.

 

예: 간선 지향 전략_크루스칼 알고리즘

 

1. 간선들을 가중치에 의해 정렬한다.

2. (a,b)가 가중치가 가장 작으므로 선택하여 T에 추가하고, 정점 a와 b를 합친다.

3. 남은 간선들 중 (d,e)가 가중치가 가장 작으므로 선택하여 T에 추가하고 그래프의 정점 d와 e를 합친다.

4. 남은 간선들 중 (a, e)와 (b, e)가 가중치가 가장 작으므로 임의로 (a, e)를 선택하여 T에 추가하고 그래프의 정점 ab와 de를 합친다.

5. 남은 간선들 중에 가중치가 가장 작은 (b,e)는 이미 합쳐진 정점들 사이의 간선이므로 버린다.

6. 남은 간선들 중에 (c,e)가 가중치가 가장 작으므로 선택하여 T에 추가하고 abde와 c를 합친다. 모든 정점들이 합쳐졌음으로 종료한다.

 

단일 출발점 최단 경로 찾기 _ 다익스트라 알고리즘

■ 아이디어 : 출발 정점 v0부터 가까운 순서로 다른 정점들까지의 최단 경로를 찾는다.

< 1단계 > : 출발 정점 0과 연결된 정점은 1과 4이다. 

0 - 1 : 2(최소)이고 0 - 4는 7이다. 따라서 (0,1)을 선택.

< 2단계 > : 0과 1이랑 연결되어 있는 정점은 2와 4이다.

2로 가는 길 : 0 - 1 - 2 : 2+5 = 7

4로 가는 길 

: 0 - 4 : 7

: 0 - 1 - 4 : 2 + 1 =3(최소)  따라서, 4를 연결한다.

< 3단계 >

2로 가는 길

: 0 - 1 - 2 = 2 + 5 = 7  ,   0 - 1 - 4 - 2 = 2 + 1 + 3 = 6(최소)

3으로 가는 길

: 0 - 1 - 4 - 3 = 2 + 1 + 6 = 9

< 4단계 >

3으로 가는 길

: 0 - 1 - 4 - 3 = 2 + 1 + 6 = 9(최소)  ,  0 - 1 - 4 - 2 - 3 = 2+1+3+4 = 10