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

0. 최단 경로

최단 경로
간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로

• 하나의 시작 정점에서 끝 정점까지의 최단 경로
  • 다익스트라(Dijkstra) 알고리즘
    • 음의 가중치를 허용하지 않음
  • 벨만-포드(Bellman-Ford) 알고리즘
    • 음의 가중치 허용
• 모든 정점들에 대한 최단 경로
  
  • 플로이드-워샬(Floyd-Warshall) 알고리즘

이번에는 이 중에서 다익스트라( Dijkstra) 알고리즘을 알아본다.

1. 다익스트라(Dijkstra) 알고리즘

시작 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.

시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다.

그리디 기법을 사용한 알고리즘으로 정점 중심 그래프로 표현한다.

프림(Prim) 알고리즘과 유사하다.

1-1. 슈도 코드

s: 시작 정점, A: 인접 행렬, D: 시작 정점에서의 거리
V: 정점 집합, U: 선택된 정점 집합

Dijkstra(s, A, D)
	U = {s};
    
    For 모든 정점 v
    	D[v] <- A[s][v]
        
    While U != V
    	D[w]가 최소인 정점 w ∈ V-U를 선택
        U <- U ∪ {w}
        For w에 인접한 모든 미방문 정점 v
        	D[v] <- min(D[v], D[w] + A[w][v])

2. 구현

다익스트라 알고리즘은 방문 처리용 배열이 없어도 문제없이 동작한다.