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

https://blog.naver.com/ndb796/221234424646

<최단 경로 알고리즘>

- 정의 : 특정한 하나이 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌. 단, 음의 가중치를 갖는 간선을 포함하지 않음.

(현실시계에서 사용하기에 적합함.)

- 용도 : 인공위성 GPS 소프트웨어에서 가장 많이 사용됨. 왜?

- 구현에 쓰이는 알고리즘)

 (1) 다이나믹 프로그래밍을 활용.

: 최단 거리는 여러 개의 최단 거리로 이루어져있다.

따라서, 다익스트라를 이용하여 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용하여 구현함.

 (2) 그리디 알고리즘으로 분류되기도 함.

- 다익스트라 작동 과정)

 : 현재까지 알고 있던 최단 경로를 계속해서 갱신함.

  (1) 출발 노드를 설정한다. (방문)

  (2) 출발 노드를 기준으로 이웃한 각 노드의 최소 비용을 저장한다.

  (3) 출발 노드를 기준으로 이웃한 노드 중, 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.

  (4) 해당 노드를 거쳐서 이웃한 노드로 가는 경우를 고려하여 기존의 최소 비용을 갱신한다.

  (5) 모든 노드를 방문할때까지 (3)-(4)를 반복한다.

- 구현)

  (1) 그래프를 특정 행에서 열로 가는 비용을 이차원 배열 형태로 변환.