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

최단 경로

• 최단 경로 정의
  • 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로
• 하나의 시작 정점에서 끝 정점까지의 최단 경로
  • 다익스트라(dijkstra) 알고리즘
    • 음의 가중치를 허용하지 않음
  • 벨만-포드(Bellman-Ford) 알고리즘
    • 음의 가중치 허용
• 모든 정점들에 대한 최단 경로
  • 플로이드-워샬(Floyd-Warshall) 알고리즘

 

Dijkstra 알고리즘

• 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식
• 시작정점(s)에서 끝정점(t) 까지의 최단 경로에 정점 x가 존재
• 이때, 최단경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단경로 구성
• 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사

 

• 알고리즘

# 다익스트라 알고리즘
def dijkstra(s, adj):

    sel = [s]           # 최소거리 정점 탐색 완료 리스트
    d = list(adj[s])    # 출발정점에서 갈 수 있는 정점들의 거리 리스트

    while len(sel) < (n + 1):   # 모든 정점이 탐색할 때 까지
        # 최소 거리 정점 탐색을 위한 초기화
        min_d = float('inf')
        idx = -1

        # 전체 정점 번호를 순회
        for i in range(n+1):
            # i번째 거리가 min_d 보다 작고, 아직 i가 탐색이 완료되지 않았을 경우
            if d[i] < min_d and i not in sel:
                min_d = d[i]
                idx = i

        # idx에 대해 탐색 결정
        sel.append(idx)

        # idx 정점으로부터 인접 정점, 인접 정점까지의 거리
        for next_v, next_d in enumerate(adj[idx]):
            # idx 정점으로부터 갈 수 있고 (inf가 아니고) 이미 저장되어있는 거리보다 가까울 경우
            if next_d != float('inf') and d[next_v] > d[idx] + next_d:
                # 경유해서 가는 짧은 거리로 갱신
                d[next_v] = d[idx] + next_d

    return d[-1]


for tc in range(1, int(input())+1):
    n, e = map(int, input().split())

    adj = [[float('inf')] * (n+1) for _ in range(n+1)]
    for i in range(e):
        n1, n2, w = map(int, input().split())
        adj[n1][n2] = w

    print(f'#{tc} {dijkstra(0, adj)}')

 

• 알고리즘 예시

시작 정점 거리 0으로 초기화

인접 정점 b로 갈 수 있는 거리중 최단 거리로 초기화

b와 인접한 정점까지의 최소 거리 비교 및 갱신 (c의 경우 동일, d의 경우 갱신)

정점 c와 인접한 정점까지의 거리 비교

정점 d와 인접한 정점까지의 거리 비교

정점 e와 인접한 정점까지의 거리 비교

모든 정점에 대해서 최단 경로 탐색 완료

정점 a에서 f까지 가는 최단 경로는 위의 그래프와 같음