다익스트라(Dijkstra) 정확성 증명

앞서 최단거리 알고리즘으로 Prim, Kruskal 을 다뤄보았다. 이번 포스팅에서 다룰 Shortest Path 알고리즘은 다익스트라(dijkstra)이다. 다익스트라 알고리즘이 왜 정확한지 정확성 증명을 해보고, 코드로 구현을 해보겠다. Dijkstra Algorithm 정확성 증명 Source 노드에서 시작 각 노드에 적힌 숫자는 source 노드와의 최단거리를 나타낸다. 정답을 찾아가면서 이 노드들의 숫자를 update 하면 된다. 다익스트라의 특징 모든 노드에서 시작점까지의 최단 거리를 구할 수 있다. 단순히 거리만 구하는 것이 아니라, 지나온 경로도 알 수 있다. (백 트래킹) 진행 방법 위처럼 노드들이 있고, 노드마다 적힌 숫자는 시작 노드와의 최단거리를 나타낸다. 빨간 영역은 알고리즘에 의..

2022.10.06