[알고리즘] 모든 정점 간의 최단 경로

두 정점 간의 최단 경로(shortest path)는 가중 방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로를 의미한다.

모든 정점 간의 최단 경로는 주어진 그래프에서 경로의 길이, 즉 가중치의 합이 음수인 사이클은 없다고 가정한다.

 

모든 정점 간의 최단 경로를 구하는 대표적인 알고리즘으로 플로이드(Floyd)알고리즘이 있다.

플로이드 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 한꺼번에 구하는 알고리즘으로, 간선의 인접 행렬 표현을 활용하여 경유할 수 있는 정점의 범위가 1인 경로부터 시작해서 1부터 |V|까지 인 경로까지 단계적으로 범위를 늘려 가면서 모든 정점 간의 최단 경로를 구하는 알고리즘이다.

 

---

예제 1

다음과 같이 네 개의 정점과 다섯개의 간선으로 구성된 방향 그래프가 입력으로 주어질 때 모든 정점 간의 최단 경로를 구하시오.

답) [

[0, 1, 2, 무한],

[무한, 0, 5, 무한],

[무한, -1, 0, 무한],

[3, 4, 5, 0]

]

---

모든 정점 간의 최단 경로의 길이를 구하는 플로이드 알고리즘

function solution1(D){
    for(let k=0; k<D.length; k++){
        for(let i=0; i<D.length; i++){
            for(let j=0; j<D.length; j++){
                let sum = D[i][k]+ D[k][j];
                if(D[i][j] > sum) D[i][j] = sum;
            }
        }
    }
    return D;
}

let arrD = [
    [0, 4, 2, 10],
    [10, 0, 5, 10],
    [10, -1, 0, 10],
    [3, 10, 10, 0]
];
console.log(solution1(arrD));

무한대를 표시하기 애매해서 10으로 표현 했습니다.

그래서 답이 좀 이상하게 나옵니다.

0: (4) [0, 1, 2, 10]
1: (4) [10, 0, 5, 10]
2: (4) [9, -1, 0, 9]
3: (4) [3, 4, 5, 0]

 

그래서 k=1일 때

D[3][1] = min[D[3][1], D[3][2]+D[2][1]] = min[무한, -1+무한] = 무한

D[3][4] = min[D[3][4], D[3][2]+D[2][4]] = min[무한, -1+무한] = 무한

 

무한에 -1를하든 +2를 하든 다 무한이 되는데

여기서는 제가 10으로 표현 대서 연산이 돼서 10이 아닌 9로 바뀌었습니다.