다익스트라 알고리즘 Dijkstra's algorithm 일정 시간 복잡도

다익스트라 알고리즘은 시작 정점이 정해져있다. 

 

정점을 선택해가며 진행하고 각 정점까지 총 가중치를 합한 값을 저장하고 비교해 나간다.

 

앞서 살펴본 프림 알고리즘의 일정 시간 복잡도와 유사하다.

T(n) = 2(n-1)(n-1)로 

모든 정점을 방문하기 위해서는 시작 정점을 제외하고 n-1개의 정점을 방문해야한다.

 

그러므로 repeat n-1번을 해준다 (가장 바깥쪽 반복문)

 

이 repeat내부에서는 

각 정점까지 현재 진행상태에서의 최단거리를 비교하고 (n-1번)

 

이동할 정점을 고른 후에는 다시 각 정점까지의 거리를 업데이트한다 (n-1번)

 

그렇기 때문에 (n-1 + n-1)(n-1) = 2(n-1)(n-1)이 되는 것이다.

 

 

 

 

의사 코드를 보면 다음과 같다. 

void dijkstra(int n, const number W[][]. set_of_edges& F)
{
    index i, vnear;
    edge e;
    index touch[2..n];
    number length[2..n];
    
    F = ∅ //방문 간선 초기화
    for(i = 2; i <= n; i++){  //1번 정점에서 시작하기 위한 초기화
        touch[i] = 1;
        length[i] = W[1][i];
    }
    
    repeat(n-1 times) //start제외 n-1개의 정점을 모두 방문할 때까지 반복
    {
        min = ∞;
        for(i = 2; i <= n; i++)
        {
            if(0 <= length[i] < min) //해당 정점까지의 최단 거리 선택하기
            {
                min = length[i];
                vnear = i;
            }
        e = edge from vertex indexed by touch[vnear] to vertex indexed by vnear;
        add e to F;
        for(i = 2; i <= n; i++) //거리 업데이트
        {
            if(length[vnear] + W[vnear][i] < length[i])
            {
                length[i] = length[vnear] + W[near][i];
                touch[i] = vnear;
            }
        length[vnear] = -1; //방문 한 곳 처리
        }
    }