최단경로 알고리즘
에지에 가중치가 주어진 방향 그래프에서 경로의 길이는 경로 상에 있는 에지 가중치 합이다.
이 합이 가장 작을 때 ‘최단 경로’라고 한다.
다익스트라 알고리즘
음수 가중치가 없다고 가정한 단일-소스 최단 경로 알고리즘, prim알고리즘처럼 S가 처음 주어지고 T영역으로 S를 확대해 나가는 알고리즘
(Tip) s'(소스)로부터 해당 정점까지 거리를 합하여 작은 것을 선택하는 것이 포인트
구현 방법 및 시간 복잡도
prim알고리즘의 테이블 논리를 그대로 이용함. -> O(n^2)
단, w열을 (s’로부터 누적해서 계산한 값)으로 업데이트 함.
prim table의 w열은 Length열로, vertex열은 parent열로 변경됨을 주의!!
다익스트라 알고리즘 구현
#include <stdio.h> #include <stdlib.h> #include <limits.h> #define TRUE 1 #define FALSE 0 #define MAX_VERTICES 100 #define INF 1000000 typedef struct GraphType { int n; int weight[MAX_VERTICES][MAX_VERTICES]; }GraphType; int L[MAX_VERTICES]; // <테이블의 w열> , 원소: s집합에서 해당 정점까지의 누적 거리 int selected[MAX_VERTICES]; // <테이블의 s/t열> , 선택되면 s집합에 속함 // 현재 테이블(s/t,L) 상태 출력 void print_status(GraphType* g) { printf("\nS/T: "); for (int i = 0; i < g->n; i++) printf("%2d ", selected[i]); printf("\n"); printf("Length: "); for (int i = 0; i < g->n; i++) { if (L[i] == INF) printf("INF "); else printf("%2d ", L[i]); } printf("\n"); } // s집합에 속하지 않으면서 최소 w[v] 값을 갖는 정점을 반환 int get_min_vertex(int n) { int v, i; // 선택되지 않은 정점을 선택 (v정점 지정) for (i = 0; i < n; i++) { if (!selected[i]) { v = i; break; } } // v정점의 w값과 나머지 정점들의 w값을 비교하면서 최소 w값을 갖는 정점 구하기 (선택된 것은 제외) for (i = 0; i < n; i++) { if (!selected[i] && (L[i] < L[v])) v = i; } return v; } void shortest_path(GraphType* g, int start) { int i, u, w; // s집합이 시작 정점(0)만 있을 때 테이블을 생성 <정점 1개 선택 됨> for (i = 0; i < g->n; i++) { L[i] = g->weight[start][i]; selected[i] = FALSE; } selected[start] = TRUE; // s집합을 확대해 나가면서 테이블을 업데이트 <선택할 정점이 없거나, n-1개의 정점이 선택될 때까지> for (i = 0; i < g->n - 1; i++) { print_status(g); // L배열에서 가중치가 가장 작은 정점 선택 (s에 속하지 않은 정점들로 한정) u = get_min_vertex(g->n); selected[u] = TRUE; if (L[u] == INF) { printf("-> 선택할 정점이 없음\n"); return; } else printf("-> 정점 %d 선택\n", u); // s집합과 인접한 정점들로 L배열 업데이트 for (w = 0; w < g->n; w++) { if (!selected[w]) { // u정점을 기준으로 인접한 것을 찾음 <u정점 말고 다른 정점도 s집합에 속하지만 같은 배열을 업데이트하는 개념이므로, 이미 처리가 된 상태임> if (g->weight[u][w] != INF) { // prim때와는 달리 누적 거리를 계산함 if (L[u] + g->weight[u][w] < L[w]) L[w] = L[u] + g->weight[u][w]; } } } } } int main(void) { // 가중치를 포함한 방향 그래프 (연결 못하면 INF) GraphType g = { 6,{ {0,50,10,INF,45,INF}, {INF,0,15,INF,10,INF}, {20,INF,0,15,INF,INF}, {INF,20,INF,0,35,INF}, {INF,INF,INF,30,0,INF}, {INF,INF,INF,3,INF,0}, } }; shortest_path(&g,0); return 0; }
2 thoughts on “Data Structure – Dijkstra Algorithm”
Hello! Someone in my Myspace group shared this site with us so I came to check it out.
I’m definitely loving the information. I’m bookmarking and will be tweeting this
to my followers! Terrific blog and wonderful design.
Greetings! I know this is kind of off topic but I was wondering which blog platform are you using
for this site? I’m getting tired of WordPress because I’ve had issues with hackers and I’m looking at alternatives for another platform.
I would be great if you could point me in the direction of
a good platform.