Dijikstra Algorithm-다익스트라 알고리즘, 최단거리 알고리즘

Dijikstra Algorithm이란?

다익스트라 알고리즘은, 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이다.

일반적으로 잘 알려져 있는 방식은, 한 꼭짓점을 '소스' 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지 최단경로를 찾는다.

알고리즘 구현 방식

시작할 노드를 초기점으로, 꼭짓점 Y의 거리를 초기점에서 Y까지의 거리로 정의한다. 다익스트라 알고리즘은 초기 거리값을 부여하고,

단계를 거듭하며 개선시킨다. 이 것을 간선완화(edge relaxation)이라고 한다.

1. 모든 노드를 미방문상태(NULL)로 표기.

2.모든 노드에서 미방문 인접 꼭짓점을 찾아 그 시험적거리를 현재 노드에서 계산한다. 새로 계산한 시험적거리를 현재 부여된값과 비교하여 더 작은 값을 추적한다.

4.만약 현재 노드에 인접한 모든 미방문 꼭짓점까지의 거리를 계산했다면, 현재 노드으로 방문한 것으로 표기하고, 미방문 집합에서 제거한다. 방문한 노드는 재방문하지 않는다.

5.두 노드 사이의 경로를 찾는 경우; 도착점이 방문한 상태로 표기되면 멈추고 알고리즘을 종료한다.

6.완전 순회 경로를 찾는 경우; 미방문집합에 있는 노드들의 시험적 거리 중 최솟값이 무한대이면 이는 출발점과 미방문 집합 사이에 연결이 없는 경우이므로 멈추고 알고리즘을 종료한다. 아니면 시험적 거리가 가장 작은 다음 미방문 노드를 새로운 '현재위치'로 선택하고 3단계로 되돌아가 반복한다.

 

알고리즘 표현<C>

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define V 9 //그래프의 정점 개수

//최소 정점을 찾는 function
int minDistance(int dist[], bool sptSet[])
{
    //최소값의 초기값
    int min=INT_MAX, min_index;
    
    for(int v=0; v<V; v++)
    {
        if(sptSet[v]==false && dist[v]<=min)
        {
            min=dist[v], min_index=v;
        }
    }
    return min_index;
}

//구성된 거리를 출력하는 function
void printSolution(int dist[])
{
    printf("Vertex \t\t\t\tDistance from Source\n");
    for(int i=0; i<V; i++)
        printf("%d \t\t\t\t %d\n",i,dist[i]);
}

//다익스트라의 단일 소스 구현 function
//인접 행렬 표현을 나타냄
void dijikstra(int graph[V][V], int src)
{
    int dist[V]; //배열 출력
    bool sptSet[V];

    for(int i=0; i<V; i++)
    {
        dist[i]=INT_MAX, sptSet[i]=false;
        dist[src]=0;
    }
    for(int cnt=0; cnt<V-1; cnt++)
    {
        int u=minDistance(dist,sptSet);
        sptSet[u]=true;
        for(int v=0; v<V; v++)
        {
            if(!sptSet[v]&&graph[u][v]&& dist[u] != INT_MAX&& dist[u]+graph[u][v]<dist[v])
            {
                dist[v]=dist[u]+graph[u][v];
            }
        }
    }
    printSolution(dist);
}

int main()
{
    int graph[V][V]= {  { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
                        { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
                        { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
                        { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
                    { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
                        { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
                        { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
                        { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
                        { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
    //funtion call
    dijikstra(graph,0);

    return 0;
}

//위 프로그램은 geeksforgeeks에 게시된 게시물을 인용했습니다.

출력결과]

 

Reference

geeksforgeeks

wikipia