graph

[Algorithm] 최단 경로 알고리즘(Shortest Paths) - 다익스트라

이번 포스팅의 주제는 최단 경로 알고리즘이다. 그래프 상에서 특정 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘인데, 대표적인 알고리즘으로 오늘 알아볼 다익스트라 알고리즘과, 추후 포스팅 할 예정인 플로이드-워셜 알고리즘, 벨만-포드 알고리즘이 있다. 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 그리디 알고리즘의 한 형태이다. 알고리즘의 진행 과정은 아래와 같다. 초기 distance table의 값을 모두 INF 값으로 설정해 주고, 시작 노드의 값만 0으로 설정한다. 현재 distance table에서 아직 방문하지 않았으며, 남은 경로 중 가장 경로가 짧은 노드에 대해서 검사를 진행한다.(초기의 경우 시작 노드) 현재 노드와 인접한 노드들을 검사한다. 현재 노드까지의 최단 경로..