211027수 - 최단경로 알고리즘,

211027수 - 최단경로 알고리즘,

### 복습필요!! ###

1. 최단 경로 알고리즘의 이해

: 두 노드를 잇는 가장 짧은 경로를 찾는 문제

: 가중치 그래프 에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적

1) 단일 출발 및 단일 도착 최단 경로 문제

2) 단일 출발 최단 경로 문제 (특정 노드와 각각 노드간에 최단 짧은 경로)

3) 전체 쌍 최단 경로 ( 그래프 내의 모든 노드와 노드 의 경우의 수에 대한 최단 경로)

2. 최단 경로 알고리즘 - 다익스트라 알고리즘

: 단일 출발 최단 경로문제.

: 특정 출발점을 가지고 그래프에 있는 각각의 노드와 특정 출발점간에 최단 경로를 다중으로 구해줌.

- 다익스트라 알고리즘 로직

- 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법.

- 너비우선탐색과 유사. (뎁스별로 탐색)

( 기준 정점과 연결되어 있는 정점(가장 얕은 뎁스)들 부터 탐색, 각각의 정점에서 연결되어 있는 정점들 계산)

- 우선순위 큐를 사용

1) 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장

- 초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장함(inf)

- 우선순위 큐에 (첫 정점, 거리0) 만 먼저 넣음

2) 우선순위 큐에서 노드를 꺼냄

- 처음에는 첫 정점만 저장되어 있으므로, 첫 정점이 꺼내짐.

- 첫 정점에 인점합 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점까지의 거리를 비교한다.

- 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣는다.

-- 결과적으로 너비우선탐색방식과 유사하게, 첫 정점에 인접한 노드들을 순차적으로 방문하게 됨.

3) 2번의 과정을 우선순위 큐에 꺼낼 노드가 없을 때까지 반복다.

from http://jun01.tistory.com/98 by ccl(A) rewrite - 2021-10-29 00:26:06