[Algorithm] 다익스트라 알고리즘 : 최단 경로 탐색(1) - 배열

인트로 다익스트라 알고리즘은 그래프의 탐색 알고리즘으로 BFS가 가중치 없는 그래프의 최단경로를 찾는 알고리즘이라면 다익스트라 알고리즘은 가중치가 있는 그래프의 최단경로를 구할 때 사용된다. 참고로 다익스트라 길 찾기 알고리즘은 DFS, BFS와 마찬가지로 완전 탐색 알고리즘에 속한다. 다익스트라(Dijkstra) 이해하기 1) 아래와 같은 가중치 그래프가 있다. 0번 정점에서 시작해 5번 정점까지의 최단거리를 구해보자. 최단거리를 저장할 배열(DIST)이 다음과 같은 형태로 있다. DIST[ ∞, ∞, ∞, ∞, ∞, ∞ ] (+ 아직 최단거리를 모르니 모두 ∞로 초기화한다.) 2) 시작 정점인 "0"번 정점을 방문한다. 시작 정점인 "0"번 정점은 최단거리가 "0"이므로 DIST[ 0, ∞, ∞, ∞..