그래프 (4) 다익스트라 알고리즘

다익스트라 알고리즘은 그리디 알고리즘이며, 그리디 알고리즘이 최적해를 보장하는 몇 안되는 경우 중 하나이다.

 

다익스트라 알고리즘은 그래프와 시작 버텍스를 인풋으로 받아 시작 버텍스로부터 이를 제외한 모든 버텍스들로 가는 최단 경로로 구성된 spanning tree를 구성한다. 이 과정에서 시작 버텍스를 subgraph로 두고 이 subgraph를 점점 확장시킨다. 다익스트라 알고리즘은 또한 모든 노드에 대해 시작 노드로부터의 거리, 즉 distance를 저장한 테이블이 필요하다. subgraph를 확장시킬 때마다 그 인접한 노드의 distance를 줄일 수 있는지 확인하고 줄인다. 이를 relaxation이라 한다.

 

의사코드

def djikstra_algorithm(G, s):
    S = {s}
    
    # distance initialization
    distance = { all infinite }
    for v in nodes of G:
        distance[v] = weight(s, v)
        
    for _ in range(|V| - 1):
        v = node that has minimum distance and not in S
        S = S U {v}
        for w in vertex not in S:
            if weight(v, w) + distance[v] < distance[w]:
                distance[w] = weight(v, w) + distance[v]

 

 

프림 알고리즘은 위 코드에서 마지막 두 줄만 수정하면 된다.

def prim_algorithm(G, s):
    S = {s}
    
    # distance initialization
    distance = { all infinite }
    for v in nodes of G:
        distance[v] = weight(s, v)
        
    for _ in range(|V| - 1):
        v = node that has minimum distance and not in S
        S = S U {v}
        for w in vertex not in S:
            if wieght(v, w) < distance[w]:
                distance[w] = wieght(v, w)

 

두 알고리즘 모두 O( |E|log|V| )의 시간 복잡도를 가진다.