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

0. 다익스트라 알고리즘이란? 다익스트라 알고리즘(dijkstra algorithm)은 그래프 상에서 시작 노드를 기점으로 다른 노드로 가는 최단 경로를 탐색하는 대표적인 최단 경로(shortest path) 탐색 알고리즘입니다. 간단하게 말해서 다익스트라 알고리즘을 사용하면, 하나의 노드에서 그래프 내의 모든 노드로 가는 최단 경로를 구할 수 있습니다. 다만, 다익스트라 알고리즘을 사용해서 최단 경로를 탐색하기 위해서는 그래프 내에 음의 간선이 포함돼서는 안된다는 점을 유의해야 합니다! 1. 다익스트라 알고리즘 동작 과정 설명 (그림으로) 다음과 같은 그래프를 예로 들어보겠습니다. 1 2 3 4 5 6 0 시작 지점을 1번 노드라고 생각하고, 위 그래프에서 다익스트라 알고리즘을 따라 최단 경로를 찾아가는 방식으로 설명해 보도록 하겠습니다. 1번 노드를 우선 방문한 후에 인접한 노드인 2, 5번 노드에 대해서 최단 경로를 갱신해 줍니다. 1번 노드와 인접한 두 개의 노드는 아직 한 ...

원문링크 : [알고리즘] 다익스트라(Dijkstra) 알고리즘, 최단 경로 탐색 알고리즘