Greedy 알고리즘 -Dijkstra 알고리즘

Greedy 알고리즘의 세 번째 문제

3.최단 경로 찾기 문제

-주어진 가중치 그래프에서 '어느 한 출발점'에서 '또 다른 도착점'까지의 최단 경로를 찾는 문제

-weight값이 양수일 때!

 

 

-대표적인 알고리즘

다익스트라(Dijkstra)최단 경로 알고리즘

주어진 출발점에서 시작하여 최단 거리가 확정되지 않은 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고, 그 점의 최단 거리를 확정

앞선 최소 신장 트리와 비교했을때, 무조건 weight가 적은 노드를 찾는 MST와는 달리 특정 경로를 향해 거쳐갈 수 있는 경로 중에서 가장 weight가 적은 것을 선택해야 한다. 여기서 Greedy 개념에 Dynamic programing 성격을 가진다. 

서울에서 대구로 가는 최소 경로를 찾을 때, 출발점 기준 가장 가까운 노드는 천안이나, 실제로 가까운 경로는 원주를 거쳐가야한다.

 

-방법

Prim 알고리즘과 비슷하게 최소 거리를 저장해두는 배열 D를 생성한다. 천안까지 가는 길이 최소 경로임을 저장해놓되, 원주를 거쳐가는 길이 있음을 삭제하지 않고 남겨둔다.

 

1.

서울에서 출발한다 가정했을 때 처음 distance table에는 서울에만 거리 0을 넣어준다. 선택된 노드 테이블에 서울을 넣은 후, 서울에서 갈 수 있는 distance table이 업데이트된다. 여기서는 천안과 원주까지의 거리가 업데이트된다.

일단 서울에서의 거리가 가까운 것은 천안이므로 천안을 선택한다.(선택되었다면 최단 거리가 픽스된 것이다.) 그 후 천안에서 갈 수 있는 distance table이 업데이트된다. 이때, 서울-원주 최소경로를 없애지 않고 그대로 둔다. 

위 그래프에 따라 천안에서는 논산과 대전까지 갈 수 있다. distance table에 서울-천안-논산, 서울-천안-대전 과 같이, 천안까지의 거리와 논산 혹은 대전까지의 거리를 합해서 업데이트해준다. 이것이 경로를 나타내는 알고리즘인 이유이다.

모든 거리를 업데이트하였는데, distance table에서 거리 값을 비교해보았을때, 선택되지 않았으면서 서울에서 가장 가까운 노드는 원주이다. 그러면 다시 원주를 거치는 경로를 살펴봐야 한다. 천안이 선택되었다고 원주 경로를 없애지 않은 이유이다. 원주를 선택한다. 원주에서 갈 수 있는 노드는 강릉과 대구이다. 원주까지의 거리를 합해서 서울-원주-대구, 서울-원주-강릉 경로를 distance table에 업데이트한다.

선택되지 않았으면서 서울에서 가장 가까운 노드는 이제 논산이다. 논산에서 갈 수 있는 노드는 광주와 대전이다. 서울-천안-논산-대전, 서울-천안-논산-광주 경로를 distance table에 업데이트해주는데, 대전은 기존 distance 값이 있다. 그러면 어떤 값이 최소 경로인지를 비교해서 업데이트 하거나 그대로 둘 수 있다. 위 그래프에서는 업데이트를 해주었다. 그러면 서울에서 출발했을 때 천안에서 바로 대전으로 가는 것보다 논산을 거쳐 대전으로 가는 것이 빠르다는 말이 된다.

같은 방식으로 대전을 선택하고 table을 업데이트했다. 이번엔 기존 distance가 최소이므로 업데이트하지 않았다.

모든 노드를 선택할때까지 반복해준다. 

T={서울,천안,원주,논산,대전,대구,광주,부산,강릉,포항}

D={} 라는 결과물이 나온다.

 

 

-Pseudo Code

Input: 가중치 그래프 G=(V,E), |V|=n,|E|=m

Output:출발점 s로부터 (n-1)개의 점까지 각각 최단 거리를 저장한 배열 D

배열 D를 초기화. 단 D[s]=0.
while(s로부터 최단거리가 확정되지 않은 점이 있으면){
  최단거리가 없는 점v에 대하여 최소의 값을 가진 점을 선택하고, 최단거리를 확정
  현재보다 짧은 거리로 우회 가능한 각 점 w에 대하여 D[w]를 갱신
}
return D

 

-Prim vs Dijkstra 

둘다 Greedy search+Dynamic search 요소가 합쳐져있다는 공통점이 있다.

그러나 MST는 노드의 선분만을 저장하고, 최단경로 문제는 선분의 합을 저장해야한다. 농축된 weight라고 할 수 있다.

MST는 랜덤으로 출발지를 선택하는 문제이고, 최단경로는 출발지가 확실하게 정해져있어야 한다.

 

-Dijkstra의 Time Complexity

1.초기화하는 부분은 constant하므로 제외

2.최단거리가 확정되지 않으면 계속해서 순환하므로 n번.O(n)

3.순환 안에서 가중치 그래프 G의 값 중 최소값을 찾아 그래프를 순환하므로 n-1번.O(n-1)

4.2번 순환 안에서 3번에서 찾은 최소값을 D의 값과 비교했을 때 최소값인지 비교하기 위해 배열을 순환하므로  O(n)

 

Time Complexity= O(1)+O(n*(2n))

 

n번 순환이 2n번 반복되므로 O(n^2) 시간복잡도를 가진다.

 

-소스 코드

#include <stdio.h>

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 10  // 노드 개수
#define INF 1000    // INFINITE

int weight[MAX_VERTICES][MAX_VERTICES] = {//가중치 그래프를 배열로 표현
  {0,INF,INF,INF,INF,INF,INF,21,INF,25},//강릉
  {INF,0,13,INF,INF,15,INF,INF,INF,INF},//광주
  {INF,13,0,INF,3,INF,INF,INF,4,INF},//논산
  {INF,INF,INF,0,10,9,INF,7,INF,19},//대구
  {INF,INF,3,10,0,INF,INF,INF,10,INF},//대전
  {INF,15,INF,9,INF,0,INF,INF,INF,5},//부산
  {INF,INF,INF,INF,INF,INF,0,15,12,INF},//서울
  {21,INF,INF,7,INF,INF,15,0,INF,INF},//원주
  {INF,INF,4,INF,10,INF,12,INF,0,INF},//천안
  {25,INF,INF,19,INF,5,INF,INF,INF,0}//포항
};
int selected[MAX_VERTICES];  // 방문한 정점 표시
int distance[MAX_VERTICES]; // 시작 정점으로부터의 최단 경로 거리

int choose(int distance[], int n, int selected[])
{
    // 현재 distance 배열에서 가장 작은 값을 가지는 노드의 index를 반환한다.

    int i, min, v;//최소값과, 그 인덱스를 저장할 변수
    min = INF;
    v = -1;

    //distance의 선택되지 않은 노드 중에서 최소값을 찾는다.
    for (i = 0; i < n; i++)
    {
        
        if (distance[i] < min && selected[i] == FALSE)//선택되지 않았고 min값보다 작다면
        {
            min = distance[i];//min에 대입
            v = i;//min 값의 인덱스 저장
        }
    }
    return v;//인덱스 반환
}

void printD() {
    printf("D:");//업데이트할때마다 배열 distance 출력
    for (int i = 0; i < MAX_VERTICES; i++)
    {
        printf("%d ", distance[i]);
    }
    printf("\n");
}
void ShortestPath(int s, int n)
{
    int i, u, w;

    //distnace와 selected 초기화
    for (i = 0; i < n; i++)
    {
        //출발점 기준으로 distance 배열을 초기화 한다. 출발지에서 출발지까지 0, 천안, 원주 이동가능
        distance[i] = weight[s][i];

        //모든 노드 선택되지 않음
        selected[i] = FALSE;
    }
    // 시작 노드 선택됨
    selected[s] = TRUE;
    distance[s] = 0;
    printf(" %d 방문 ", s);
    printD();

    for (i = 0; i < n - 1; i++) {//시작 노드 제외하고 노드 개수만큼 반복
        //배열 D에서 최소값을 찾는다.
        u = choose(distance, n, selected);//최소값의 인덱스는 u

        //찾은 점을 선택한다. 선택 여부 저장한다.
        selected[u] = TRUE;

        printf(" %d 방문 ",u);
        //찾은 점 u를 집합 s에 추가, distance 업데이트
        for (w = 0; w < n; w++)
        {
            if (selected[w] == FALSE)//선택되지 않아야 하고,
            {
                //모든 점에 대하여, 현재 출발지까지의 거리가 기존 출발지까지의 거리보다 가깝다면 업데이트해준다.
                if (distance[u] + weight[u][w] < distance[w])
                {
                    distance[w] = distance[u] + weight[u][w];
                }
            }
        }
        printD();//업데이트할때마다 배열 D출력
    }
}

void main()
{
    ShortestPath(6, MAX_VERTICES);// 출발지부터 N노드까지의 최단경로를 찾아라. 서울-부산
}