Dijkstra (1) 썸네일형 리스트형 115. Dijkstra 다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프에서 정점과 정점 사이의 최단 경로를 찾을 때 가장 많이 사용되는 알고리즘으로, 유향 그래프와 무향 그래프에서 모두 사용할 수 있으나 가중치가 음수인 간선이 없는 그래프에서만 정상적인 작동을 보장할 수 있다. 다익스트라 알고리즘은 기본적으로 시작 정점이 하나로 고정되어 있으며 작동 원리는 다음과 같다. 1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다. 2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 때 $w(x, y) = z$라고 한다. 3. $d_k$는 $0$, 나머지 $d_i$는 모두 $\infty$로 초기화한다. 4. 아직 선택하지 않은 정점들 중 $d_i$값이 가.. 이전 1 다음
