5. 잘 알려진 알고리즘 분석

5.1. 다익스트라(Dijkstra)

다익스트라 알고리즘 은 그래프에서 한 정점에서 다른 정점까지의 최단거리 또는 경로를 구할 수 있는 알고리즘이다.

본 알고리즘은 SPT(Shortest Path Tree)와 NSPT(가칭, Not Shortest Path Tree)를 이용하여 설계되었다. 초기 NSPT는 입력된 그래프를 뜻한다. NSPT의 각 정점들은 최단거리를 저장하는 공간을 갖고 있으며 무한대로 초기화한다. 단, 시작 정점은 0의 값으로 초기화 된다.

NSPT의 최단거리 값이 가장 작은 정점을 추출하여 SPT에 추가한다. 그리고 간선으로 연결된 정점들의 최단거리를 갱신한다. 전체 VSize 만큼 루프를 돌면 SPT은 최단거리 값을 갖는 그래프가 된다.

5.1.1. 시간 복잡도

인접행렬로 구현한다면 최악의 시간복잡도 V^2이 걸린다.

5.1.2. 루프 불변성

알고리즘은 i=1 … vsize 만큼 루프를 돌게 된다. SPT에 존재하는 i-1개의 각각 정점은 시작정점 사이의 최단거리 거리를 저장한다. 이라는 명제는 항상 참이다.

1. i = 1 (초기조건) 일때 0개의 정점은 최단거리를 저장하고 있다.
2. 1 < i < vsize+1 (유지조건) 일때 vsize-1개의 정점은 최단거리를 저장하고 있다.
3. i = vsize+1 (종료조건) 일때 vsize개의 정점은 최단거리를 저장하고 있다.

루프 불변성을 지닌다. vsize+1은 종료조건이며 루프탈출 뒤이다.

5.2. Floyd Warshall Algorithm(플로이드 월쉘)

5.2.1. 루프 불변성

알고리즘에서 경유 정점 k=1 … vsize 만큼 루프를 돌게 된다. 모든 i,j에 대해 distant[i][j]는 1 ~ k-1 번째 정점을 경유한 정점중 가장 짧은 최단거리를 저장하게 된다. 이라는 명제는 항상 참이다.

1. k = 1 (초기조건) 일때 distant[i][j] 1 ~ 0번째 정점을 경유한 정점중 가장 짧은 최단거리를 저장하고 있다.
2. 1 < k < vsize + 1 (초기조건) 일때 distant[i][j] 1 ~ vsize-1 번째 정점을 경유한 정점중 가장 짧은 최단거리를 저장하고 있다.
3. k = vsize + 1 (초기조건) 일때 distant[i][j] 1 ~ vsize 번째 정점을 경유한 정점중 가장 짧은 최단거리를 저장하고 있다.

루프 불변성을 지닌다.