자료구조 :: 그래프(6) Dijkstra의 최단 경로 알고리즘

# Dijkstra의 최단 경로 알고리즘

Dijkstra의 최단 경로 알고리즘은 네트워크에서 하나의 시작 정점으로부터 모든 다른 정점까지의 최단경로를
찾는 알고리즘이다. 최단 경로는 경로의 길이순으로 구해진다.

데이크스트라 알고리즘(Dijkstra algorithm)은 네덜란드의 컴퓨터과학자 에츠허르 데이크스트라의 이름을 딴,
어떤 간선도 음수 값을 갖지 않는 방향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는
알고리즘이다.

예를 들어, 그래프의 점들이 각각 도시를 나타내고, 연결선들이 도시 사이를 연결하는 도로의 길이를 나타낸다면,
데이크스트라 알고리즘은 임의의 두 도시 사이의 최단 경로를 찾는다.

데이크스트라 알고리즘은 방향이 주어진 가중 그래프(weighted graph) G와 출발점 s를 입력으로 받는다.
그래프 G의 모든 점들의 집합을 V라 하고, 그래프의 간선을 간선의 출발점 u와 도착점 v의 쌍 (u, v)로 표현한다.
G의 모든 간선들의 집합을 E라 하고, 간선들의 가중치는 함수 w: E → [0, ∞]로 표현한다. 이때 가중치 w(u, v)는
점 u에서 점 v로 이동하는 데 드는 비용(시간, 거리 등)이 된다. 경로의 비용은 경로 사이의 모든 간선들의 가중치의
합이 된다. 데이크스트라 알고리즘은 V의 임의의 점의 쌍 s와 t가 있을 때 s에서 t로 가는 가장 적은 비용이 드는
경로(최단 경로)를 찾는다. 이 알고리즘은 주어진 출발점 s로부터 다른 모든 점까지의 최단 경로를 계산하는 데도
사용할 수 있다.

방향그래프(Directed Graph)의 간선이 양수의 Weight를 가질 때 임의의 출발 정점에서 도착 정점까지의 경로 중
경로의 길이가 최소인 경로를 최단경로라고 정의한다.
이러한 최단경로는 도로망, 항공로 지도, 작업공정계산 등에 널리 응용된다. 최단경로는 다익스트라의 알고리즘
으로 구할 수 있다.

# 다익스트라의 알고리즘

인접행렬 상태로 각 간선의 가중치(Weight)가 존재하도록 한다.
정점 i에서 i까지의 가중치는 0이고 정점 i에서 j까지의 간선 E(i, j)가 존재치 않으면 가중치는 무한대(∞)가 된다.
집합 S와 T를 정하는데 S는 출발 정점을 초기값으로 하고 집합 T는 출발 정점을 제외한 모든 정점을 포함하도록
초기화, 출발 정점을 제외한 모든 정점으로부터의 거리의 초기값(dist[i], 2<=i<=n)을 [1]의 인접행렬에서 취한다.
집합 T의 원소 중 출발점으로부터의 거리가 최소인 정점 v를 택하여 T에서 제거하고 집합 S에 추가한다.
T집합내의 모든 정점 w에 대해 출발점으로부터의 거리(dist[w])와 간선 E(v, w)의 길이에 v정점의 거리(dist[v])를
합한 값 중 작은 것을 선택하여 정점 w의 거리(disw[w])로 한다.
[4]와 [5]의 과정을 T집합이 공집합이 될 때까지 반복한다.

출처 : 위키백과

대략 이렇단다.. 각설하고..
dijkstra알고리즘은 참 인연이 많다. 2학년 알고리즘 수업시간에 지하철 최단경로 프로그램을 만들면서 인연이
닿았는데 생각보다 쉽게 써먹을 수 있어서 좋았다... 이해한게 아니라.......쩝..

2학년때 만들던 초기 소스이다.
아래 코드에서 맵,상수값,데이터,출력내용만 변경하면 다른 상황에서도 잘 동작한다.

Dijkstra.cpp

#include <stdio.h> 
#include <string.h> 

#define N 10
#define M 9999

int a[N+1][N+1]={ 
{0,0,0,0,0,0,0,0,0,0,0}, 
{0,0,1,M,M,M,M,M,M,M,M},//1
{0,1,0,1,M,M,M,M,M,M,M},//2
{0,M,1,0,1,M,M,M,M,M,M},//3
{0,M,M,1,0,1,M,M,M,M,M},//4
{0,M,M,M,1,0,1,M,M,M,M},//5
{0,M,M,M,M,1,0,1,M,M,M},//6
{0,M,M,M,M,M,1,0,1,M,M},//7
{0,M,M,M,M,M,M,1,0,1,M},//8
{0,M,M,M,M,M,M,M,1,0,1},//9
{0,M,M,M,M,M,M,M,M,1,0}};//10
// 1.2.3.4.5.6.7.8.9.10

typedefstruct { 
char *state; 
int state_num; 
}SubType; 

SubType subway[N+1]={"null",0,"신평",1,"하단",2,"당리",3,"사하",4,"괴정",5,"대티",6, 
"서대신동",7,"동대신동",8,"토성동",9,"자갈치",10}; 

int main(void) 
{ 
int j,k,p,start,end,min,i=0,count=0, 
    leng[N+1], // 정점까지의 거리
    v[N+1], //확정 플래그 
    index[N+1]; 

    start=subway[1].state_num; // 시작점 입력

for(k=1;k<=N;k++) // 초기화
    { 
        leng[k]=M;   
        v[k]=0; 
    } 

    leng[start]=0;  /* 시작점은 표시하지 않는다 */
    index[start]=0;  

for(j=1;j<=N;j++) 
    { 
        min=M; 

for(k=1;k<=N;k++) // 최단거리 정점을 찾는다
        { 
if(v[k]==0 && leng[k]<min) 
            { 
                p=k; 
                min=leng[k]; 
            } 
        } 

        v[p]=1; // 최소인 정점을 확정

if(min==M) 
        { 
            printf("그래프가 연결되어 있지 않다\n"); 
return1; 
        } 

// p를 경유해서 k에 이르는 거리가 지금까지의 최단 경로보다 작으면 갱신 
for(k=1;k<=N;k++) 
        { 
if((leng[p]+a[p][k])<leng[k])  
            { 
                leng[k]=leng[p]+a[p][k]; 
                index[k]=p; 
            } 
        } 
    } 

for(j=2;j<=N;j++) // 도착 경로 출력 함수
    { 
        p=j; 
while(index[p]!=0) 
        { 
            printf("%s -> ",subway[index[p]].state); 
            p=index[p]; 
        } 
        printf("\n");     
    } 
return0; 
}