이 알고리즘은 음의 간선이 없을 경우에만 적용할수 있다. 욕심쟁이 방법(Greedy Method)을 사용하고있다.
다익스트라 알고리즘은 1959년 컴퓨터 공학자 다익스트라(dijkstra)가 고안해 내었다(이걸로 튜링상 탐, 개2득)
- 다익스트라 알고리즘(Dijstra Algorithm)
1. 출발점이 연결된 마디 중에서 가장 가까운 마디를 선택한다.
2. 선택된 마디에 연결된 마디까지의 거리와 그 전의 마디에서 선택되지 않은 마디의 거리중 가까운것을 선택한다.
3. 모든 마디가 선택될 때까지 반복하며 도착점에 갔을때 기억된 값이 최단 거리가된다.
예를들어 아래와 같은 정점과 간선이 있고 v1에서 v7까지의 최단 경로를 구해보자
( v1->v2로 가는 가중치는 4이다, v4에서 v7로 가는 가중치는 3이다. )
이를 배열에 저장하여 표현할수 있다. a[1][2] =4 이런식으로 저장한다, 마찬가지로 a[4][7]= 3, oo는 무한대, 갈수없으므로)
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
1 |
oo |
4 |
2 |
oo |
oo |
oo |
oo |
|
2 |
oo |
oo |
oo |
1 |
1 |
oo |
oo |
|
3 |
oo |
oo |
oo |
7 |
oo |
3 |
oo |
|
4 |
oo |
oo |
oo |
oo |
oo |
oo |
3 |
|
5 |
oo |
oo |
oo |
oo |
oo |
oo |
1 |
|
6 |
oo |
oo |
oo |
oo |
oo |
oo |
5 |
|
7 |
oo |
oo |
oo |
oo |
oo |
oo |
oo |
최단 경로를 구하기위해 다익스트라 알고리즘을 좀더 풀어서 설명해보자
1. 시작점의 거리를 0으로 저장한다.
2. 아직 방문하지 않은 정점 중에서 거리가 가장 짧은 정점을 선택한다.
3. 선택된 정점 v는 최단거리가 확정
4. 선택한 정점을 통해 다른 정점까지의 거리가 짧아지는지 계산한다.
5. 모든 정점이 선택될 때까지 2~4를 반복한다.
모든 과정이 끝나있으면 시작 정점에서 모든 정점까지의 최단경로가 나온다
각 정점까지의 최단 경로를 저장하는 배열 dist 그리고 방문한 정점을 표시해주는 visit 배열이 필요하다.
(v1에서 출발하므로 최단경로는 0)
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
dist |
0 |
oo |
oo |
oo |
oo |
oo |
oo |
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
visit |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
* 정점 x까지의 최단 경로를 dist[x] 라고 정의할때,
v와 이웃한 정점 i를 연결해주는 간선 a[i][v]가 있다면 dist[i]의 거리 + a[i][v]의 가중치가 작은 i에 대해서 dist[v] = dist[i] + a[i][v]가 된다.
v1에서 가장 가까운 경로는 v1 자신이며, v1을 방문했다고 표시한다.
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
dist |
0 |
oo |
oo |
oo |
oo |
oo |
oo |
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
visit |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
v1 에서 v2까지 가장 가까운 경로는 v1에서 v2까지 가는 경로이며 가중치 합은 4이다.
즉 dist[2] = dist[1] + a[1][2] ( dist[1]까지 최단 경로 + 1에서 2로 가는 가중치합)
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
dist |
0 |
4 |
oo |
oo |
oo |
oo |
oo |
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
visit |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
v1에서 v3까지 가장 가까운 경로는 v1에서 v3로 가는 경로이며 가중치 합은 2이다.
즉 dist[3] = dist[1] + a[1][3]
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
dist |
0 |
4 |
2 |
oo |
oo |
oo |
oo |
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
visit |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
v4까지 가장 가까운 경로는 v1에서 v3로 가는 경로를 통한값이 최소값이며 가중치 합은 2이다.
즉 dist[4] = dsit[2] + a[2][4]
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
dist |
0 |
4 |
2 |
5 |
oo |
oo |
oo |
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
visit |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
이를 반복하면 아래와 같이 시작 정점에서 각 정점까지 최단 경로가 구해진다.
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
dist |
0 |
4 |
2 |
5 |
6 |
5 |
7 |
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
visit |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
c언어로 구현해보자
- #include <stdio.h>
- #define N 100
- #define INF 100000
- int a[N+1][N+1];
- int visit[N+1];
- int dist[N+1];
- int start, end;
- int n,m;
- // input 값 sample
- // 첫번째 라인에는 정점의 개수, 그리고 시작 정점, 도착 정점이 입력
- // 두번째 라인에는 정점별 간선의 입력받을 가중치의 개수(m)가 입력된다.
- // 세번째 라인부터는 정점별 간선의 입력받을 가중치가 m번이 들어온다.
- /*
- 7 1 7
- 9
- 1 2 4
- 1 3 2
- 2 4 1
- 2 5 2
- 3 4 7
- 3 6 3
- 4 7 3
- 5 7 1
- 6 7 5
- */
- void input()
- {
- int i,j;
- int from,to;
- int w;
- scanf("%d %d %d",&n,&start,&end);
- scanf("%d",&m);
- // 각 정점으로 가는 간선의 가중치를 무한대로 초기화한다.(최소값을 구하기위해)
- for ( i =1;i <=n; i++)
- for ( j =1; j <=n; j++)
- if ( i!= j)
- a[i][j] = INF;
- for ( i =1;i <= m; i++) // 정점에서 정점으로 가는 간선의 가중치가 입력
- {
- scanf("%d %d %d",&from,&to,&w);
- a[from][to] =w;
- }
- for ( i =1;i <=n; i++)
- dist[i] = INF;
- }
- void dijkstra()
- {
- int i,j;
- int min;
- int v;
- dist[start] = 0; // 시작점의 거리 0
- for ( i =1;i <=n; i++)
- {
- min = INF;
- for ( j =1 ; j <=n; j++)
- {
- if ( visit[j] == 0 && min > dist[j]) // 갈수 있는 정점중에 가장 가까운 정점 선택
- {
- min = dist[j];
- v = j;
- }
- }
- visit[v] = 1; // 가장 가까운 정점으로 방문, i정점에서 가장 가까운 최단경로 v
- for ( j = 1;j <= n; j++)
- {
- if ( dist[j] > dist[v] + a[v][j]) // 방문한 정점을 통해 다른 정점까지의 거리가 짧아지는지 계산하여 누적된값 저장
- dist[j] = dist[v] + a[v][j];
- }
- }
- }
- int main(void)
- {
- input();
- dijkstra();
- printf("%d \n",dist[end]);
- return 0;
- }