Written by nodejs-style
on 2021-09-26

다익스트라 알고리즘(Dijkstra Algorithm)

다이스트라 알고리즘

다익스트라 알고리즘 : 음의 가중치가 없는 그래프의 한 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘.

시간 복잡도 : 변의 개수를 E, 꼭지점의 개수를 V라 할 때, 이진 힙을 사용하면 O((V+E)logV)

다익스트라 알고리즘 개요:

- 시작할 꼭짓점은 초기점으로, 꼭지점 Y의 거리를 초기점에서 Y까지의 거리로 정의.

- 다익스트라 알고리즘은 초기 거리 값을 부여하고, 단계를 진행하며 최단 거리를 갱신한다. 이를 간선 완화(edge relaxation)이라고 함.

(1) 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다.

(2) 현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장한다.

(3) A로부터 갈 수 있는 임의의 노드 B에 대하여, d[A] + P[A][B]와 d[B]의 값을 비교한다. (P[A][B]는 A에서 B사이의 거리)

(4) 만약 d[A]+P[A][B]의 값이 더 작다면, 즉 더 짧은 경로라면, d[B]의 값을 이 값으로 갱신한다.

(5) A의 인접한 모든 노드에 대해 이 작업을 수행한다.

(6) A의 상태를 방문 상태로 갱신한다.

(7) 미방문 노드 중 출발점으로부터 거리가 가장 짧은 노드를 골라서 그 노드를 변수 A에 저장한다.

(8) 도착 노드가 방문 상태이거나 더 이상 미방문 노드를 선택할 수 없을 때 까지 반복한다.

Node 1 2 3 4 5 6 7 Cost 0 7 INF 5 INF INF INF

시작점을 1번으로 하였으므로 1번 노드의 거리는 0으로 갱신되고 1번 노드와 인접한 2번 노드와 4번 노드의 거리가 갱신된다.

Node 1 2 3 4 5 6 7 Visited T F F F F F F

또한 방문 여부를 저장하고 있는 방문 배열의 1번 노드가 true로 갱신된다.

Node 1 2 3 4 5 6 7 Cost 0 7 INF 5 20 11 INF

인접 노드 중 가장 거리가 짧은 4번 노드가 선택됩니다. 또한 5번과 6번으로의 경로가 갱신됩니다. 5번 노드의 경우기존의 있던 INF보다 d[4]+P[4][5]인 20이 더 작으므로 20으로 갱신되었고 6번 노드의 경우도 마찬가지로 d[4]+P[4][6]이 더 작으므로 11로 갱신됩니다.

Node 1 2 3 4 5 6 7 Visited T F F T F F F

또한 방문 여부를 저장하고 있는 방문 배열의 4번 노드가 true로 갱신된다.

Node 1 2 3 4 5 6 7 Cost 0 7 15 5 14 11 INF

인접 노드 중 가장 거리가 짧은 2번 노드가 선택됩니다. 또한 3번과 5번으로의 경로가 갱신됩니다. 3번 노드의 경우기존의 있던 INF보다 d[2]+P[2][3]인 15가 더 작으므로 15로 갱신되었고 5번 노드의 경우는 기존에 있던 20보다 d[2]+P[2][5]인 14가 더 작으므로 14로 갱신됩니다.

Node 1 2 3 4 5 6 7 Visited T T F T F F F

또한 방문 여부를 저장하고 있는 방문 배열의 4번 노드가 true로 갱신된다.