[Dijkstra] 거리간 최단거리

다익스트라란::

가치 그래프에서 임의의 두 정점간의 최단 거리를 찾아내는 알고리즘이다.

 

기본적으로 n제곱 알고리즘이며 최소힙을 사용해 과정을 줄이면 n log n까지 최적화가 가능하다.

 

모든 최단 경로는 정점과 정점 사이에 있는 정점들의 최단거리로 이루어져 있다는 것을 이용해 

 

정점간의 1차적인 최단 거리를 계산하고 새로운 정점에 이어보며 최종적인 최단거리 여부와 거리값을 계산한다.

 

 

의사코드::

 

1. 현재 정점에서 미방문이며 가장 짧은 거리를 가지고 있는 정점 X를 정한다.(정해지면 X는 방문한 정점으로 표시한다) 

 

2. 정점 X에서 갈 수 있는 정점들을 탐색하며 다음 조건을 만족하는 정점들을 탐색한다.

    ::현재 정점까지의 거리 > 현재 정점에서 X까지의 거리 + X에서 탐색한 정점까지의 거리

 

3. 2에서 탐색한 정점들의 최단거리를 갱신하고 1번으로 돌아가 과정을 최대 n-1번 반복한다.

  :: 만약 두 정점 간 최소거리를 구한다면 탐색 정점중에 도착 정점이 있는지 검사하고 있다면 탐색을 종료한다.

 

 

실제코드::

cost[1~n] = 9999;//9999는 maxvalue
cost[start] = 0;
visit[start] = 1;

for(i=1;i<=n;i++) {
    mp = 9999;
    for(j=1;j<=n;j++) {
        if(cost[j] < mp && visit[j] == 0) {
            mp = cost[j];//현재 정점에서 X까지의 거리
            mn = j;
        }//현재 정점에서 가장 적은 비용으로 이동 할 수 있는 정점을 찾아냄
    }
    
    visit[mn] = 1;
    
    for(j=1;j<=n;j++) {
        if(cost[j] > arr[mp][j] + mp) {//X와 탐색정점간의 거리계산
            cost[j] = arr[mp][j] + mp;
            if(j == end) return arr[mp][j] + mp;//두 정점간 거리 계산이라면 탐색 종료
        }
    }
}

 

간단한 그래프를 생성하고 알고리즘을 단계별로 동작시켜보자

 

 

양방향 그래프이고 1에서 5번까지의 최단 거리를 구한다.