[Algorithm Tech] 최단 경로 알고리즘

* 최단 경로 알고리즘

최소 신장 트리와 달리, 최단 경로 알고리즘은 출발 정점과 도착 정점이 존재한다.

즉, 최소 신장 트리처럼 모든 정점을 방문할 필요 없이 출발 정점에서 도착 정점까지 최단 경로만 찾으면 된다.

* 다익스트라 알고리즘    =>O(|E||log|V|)

다익스트라 알고리즘은 음의 가중치가 없을 때 우선순위 큐를 활용해 최단 경로를 구하는 알고리즘이다.

1. 출발 지점에서 시작하는 간선들 중 최소 가중치를 가지는 간선을 선택한다.

2. 해당 정점을 방문하면 해당 정점까지 필요한 가중치 + 해당 정점에서 방문할 수 있는 간선의 가중치 들을 우선순위 큐에 넣는다.

3. 위 과정을 목표 정점에 도착할 때까지 반복한다.

단, 음의 가중치가 존재해서는 안된다. => 벨만-포드 알고리즘 사용

* 벨만 - 포드 알고리즘    =>O(VE)

* 플로이드 와샬 알고리즘    =>O(n^3)

모든 경우의 수를 시도해보는 알고리즘이다.

2차원 배열 d의 초기값을 모두 무한대로 설정한다.

이후 해당 정점을 거쳐가는 최단거리가 있다면 해당 거리를 업데이트한다.

for (int k = 0; k < N; ++k) {            //거쳐가는 정점
    for (int i = 0; i < N; ++i) {        //시작 정점
        for (int j = 0; j < N; ++j) {    //도착 정점
            if (d[i][j] > d[i][k] + d[k][j]) {
                d[i][j] = d[i][k] + d[k][j];
            }
        }
    }
}

즉, d[1][5] = d[1][k] + d[k][5]가 되는데 

d[1][1] + d[1][5]  or  d[1][2] + d[2][5]  or  d[1][3] + d[3][5]  or  d[1][4] + d[4][5]  or  d[1][5] + d[5][5] 중 최소값을 찾는다.