13일차 강의 (28 ~ 29강)

플로이드 (28강)

모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘

시간복잡도 O(V^3)

음수의 가중치를 가져도 상관은 없지만, 음수의 사이클을 가지면 사용 불가

 

대입이 빈번하게 발생할 경우 min(a,b) 사용보다 if문으로 직접 비교를 통해 필요한 경우에만 대입이 일어나도록 하는 것이

시간복잡도 측면에서 더 효율적임. (DP, 플로이드 등)

 

경로복원

→ nxt테이블 이용 (최단 거리 갱신이 일어날 때 갱신)

nxt테이블을 이용해 한 단계씩 앞으로 전진하면서 경로를 복원할 수 있음

 

다익스트라 (29강)

하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘

음수인 가중치를 가지면 사용할 수 없음 (→ 벨만포드 알고리즘 이용)

 

우선순위 큐를 이용한 구현 시 시간복잡도 O(ElogE)

 

1. 우선순위 큐에 (0, 시작점)을 추가

2. 우선순위 큐에서 거리가 가장 작은 원소를 선택, 해당 거리가 최단 거리 테이블에 있는 값과 다를 경우 넘어감

3. 원소가 가리키는 정점을 v라고 할 때, v와 이웃한 정점들에 대해 최단 거리 테이블 값보다 v를 거쳐가는 것이 더 작은 값을 가질 경우 최단 거리 테이블의 값을 갱신하고 우선순위 큐에 (거리, 이웃한 정점의 번호)를 추가

4. 우선순위 큐가 빌 때 까지 2, 3번 과정을 반복

 

경로복원

최단거리 테이블이 갱신될 때 어디를 거쳐가는지 남기면 됨 (pre 테이블)

경로복원은 pre를 타고 시작점을 만날 수 있을 때 까지 계속 이동하면 됨