2018-01-02

최단경로 문제(4가지)

1 . BFS - 가중치가 없거나 동일한 그래프. 

            단일 시작점과 모든 쌍 알고리즘.

- Queue 를 이용해서 구현.

- 방문 체크 배열 (visited) => 거리 배열로 대체 가능(초기값 -1)

- 거리 배열은 distance[next] = distance[now] + 1 

2. 다익스트라 알고리즘 - 가중치가 있는 그래프. 

                                 단일 시작점과 모든 쌍 알고리즘 . 

                                 음의 가중치가 있는 경우 계산 불가.

   (엄밀히 말하면 음수 싸이클이 있는 경우 계산 불가)

   구현방법 - Priority Queue 사용, Priority Queue 사용X

##Priority Queue 를 사용할 때 , 시간 복잡도 = O(E * logV)

- 시작점의 distance 만 0을 하고 나머지는 INF 로 초기화.

- Priority Queue 에 (연결된 정점 번호, 간선 가중치) 를 pair 를 이용해 담는다.

- now 정점에서 꺼낸 가중치보다, 더 짧은 경로를 알고 있다면( distance[now] < now의 가중치), continue

- 인접한 정점들을 돌면서, 짧은 경로를 발견하면 distance 갱신한다.

- Priorty Queue 는 큰값이 우선순위가 있기 때문에, 최단 거리를 구하기 위해서 항상 가중치에 -1 을 곱해서 Queue에 담는다.

##Priority Queue 를 사용하지 않는 경우 - 정점의 갯수가 적거나, 간선의 수가 매우 많은 경우. 

                                                    (시간복잡도가 O(V^2 + E) 가 되기 때문에) 

- 방문 체크 배열(visited) 필요

- 반복문을 통해서 방문하지 않은 정점 중 , distance 값이 가장 작은 값을 찾는다.

- 그 점을 방문하고, distance 값을 계산하여 갱신한다.

3. 벨만 포드 알고리즘 - 가중치가 있는 그래프.

 단일 시작점과 모든 쌍 알고리즘.

 음의 가중치가 있는 경우 계산 가능.

 음수 싸이클이 있는 경우, 확인 가능.

 dist[v] <= dist[u] + w(u,v) 를 이용한 알고리즘

 인접리스트 - O(VE) , 인접행렬 - O(V^3)

- 각 정점까지의 최단 거리의 상화을 담은 배열 upper 필요

- 시작점의 upper 는 0, 나머지는 INF 로 초기화.

- 모든 간선에 대해서 V-1번 완화 시도

(##이유##)

음수 사이클이 없는 그래프에서 최단 경로가 한 정점을 두번 지나는 일은 없다. 

최단 경로는 최대 V개의 정점을 갖기 때문에 V-1 개의 간선을 가질 수 있으므로, 모든 간선에 대한 완화 과정은 V-1 이면 충분

- 음수 싸이클의 존재유무를 확인하기 위해서는 V-1 번의 완화 시도가 아닌 V번의 완환 시도를 통해 검증할 수 있다.

  (음수 싸이클이 없다면 V-1 번의 완화 이후에는 더 이상 완화가 일어나는 간선이 없지만, 싸이클이 있는 경우에는 완화가 계속 일어나므로)

++ BFS , 다익스트라 , 벨만 포드 알고리즘에서 실제 경로를 구하는 방법

- parent 배열을 선언하여, 갱신될 때, parent 정점을 담아준다. parent 배열을 따라가면 그게 실제 경로가 된다.

4. 플로이드-워셜 알고리즘 - 가중치가 있는 그래프.

  모든 쌍 최단 거리 알고리즘.

2차원 distance 배열을 통해서 "distance[i][j] 는 정점 i 에서 j 로 가는 최단 거리" 를 나타낸다.

시간 복잡도는 O(V^3)