FWA 2부: 플로이드 워셜 알고리즘에서 경로 복원하기

플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 노드들 간 최단 경로를 찾는 알고리즘이다.

전 글에서 소개한 플로이드 워셜 알고리즘의 구현을 그대로 가져오겠다.

    for(int x=0;x<n;x++)
    {
        for(int a=0;a<n;a++)
        {
            for(int b=0;b<n;b++)
            {
                d[a][b]=min(d[a][b],d[a][x]+d[x][b]);
            }
        }
    }

 

이는 노드 a와 b를 잇는 최단 거리를 d[a][b]에 저장하는 알고리즘이다.

 

근데 경로 그 자체는 구할 수 없다.

 

 

		d[a][b]=min(d[a][b],d[a][x]+d[x][b]);

이 부분을 보자.

d[a][b]보다 d[a][x]+d[x][b]가 작다면 d[a][b]를 그 값으로 업데이트하는 부분이다.

 

무슨 뜻이냐면 기존에 a에서 b로 가는 경로보다 a에서 x를 갔다가, x에서 b로 가는 경로의 길이가 더 짧으면 그 길을 택한다는 뜻이다.

 

최종적으로 그 길을 택했다면 a에서 b로 가는 최단거리는 x를 경유지로 가진다는 점을 알 수 있다.

 

(플로이드 워셜 알고리즘의 자세한 원리는 내 이전 글을 참고하라: https://wangdo.tistory.com/49)

 

그럼 a에서 b로 최단 경로로 갈 때 경유지를 저장하는 배열인 g[][]를 만들어보자.

g[a][b]의 값은 a에서 b로 갈 때 무조건 지나게 되는 경유지의 노드번호다.

 

이렇게 구현해볼 수 있을 것 같다.

    for(int x=0;x<n;x++)
    {
        for(int a=0;a<n;a++)
        {
            for(int b=0;b<n;b++)
            {
            	if(d[a][b]>d[a][x]+d[x][b])
                {
                	d[a][b]=d[a][x]+d[x][b];
                    	g[a][b]=x;
                }
            }
        }
    }

 

d[a][b]를 업데이트하는 부분의 논리는 달라진 것이 없다, min 함수대신 if문을 썼을 뿐이다.

그리고 x를 경유지로 가진다는 점을 안 이상 g[a][b]의 값을 x로 업데이트해준다.

 

참고로, 초기상태에서 g[][]배열에는 a에서 b로 통하는 간선이 있을 경우 a로 저장해준다.

 

만약 d[a][b]값이 한 번도 업데이트되지 않았다? -> 그렇다는 건 a에서 b로 통하는 최단거리는 a와 b를 직접 잇는 간선이 최단거리인 경우, 이때 g[a][b]값은 한 번도 건드리지 않았을 테니 g[a][b]=a일 것이다.

---

최종적으로, 특정 a에서 b로 향하는 최단 경로를 복원해보자.

 

a와 b의 최단경로가 x1을 경유지를 가진다고 해보자.

a->x1->b

 

그럼 이제 a와 x1을 잇는 최단경로의 경유지 g[a][x1]과 x1과 b를 잇는 최단경로의 경유지 g[x1][b]를 찾는다.

---

case 1. g[a][x1]=a

이 경우 a와 x1를 직접 잇는 간선이 최단 경로다.

 

case 2. g[a][x1]=x2

이 경우 경로는 a->x2->x1->b 이런 식으로 된다. 경유지가 하나 늘은 것이다.

---

직접 잇는 간선을 찾을 때까지 반복하면 된다.

void findpath(int a, int b)
{
    if(g[a][b]==a)
    {
        cout<<a<<" ";
        return;
    }
    int x=g[a][b];
    findpath(a,x);
    findpath(x,b);
}

함수로 구현한 것이다.

a에서 b까지 경로를 cout으로 출력해준다.

(다만 마지막 도착지 노드번호는 출력해주지 않으니 따로 출력해주어야 한다.

예를 들어 1->3까지 최단경로를 찾을 때, findpath(1,3)을 실행하면

최단경로가 1->2->5->8->4->3일때

1 2 5 8 4 이렇게 출력된다.)

이는 순회방법중 전위 순회(pre order)의 원리를 사용한 것이다.

 

다음은 중위 순회(in order) 원리를 이용해 구현한 함수다.

void findpath(int a, int b)
{
    if(g[a][b]==a)
    {
        return;
    }
    int x=g[a][b];
    findpath(a,x);
    cout<<x<<" ";
    findpath(x,b);
}

이 경우 출발지와 도착지를 둘 다 제외하고 cout으로 출력된다.

2 5 8 4

이런식으로 출력되는 거다.

 

당연히 후위 순회 방식도 구현 가능하다.

---

아무튼, 오늘 포스팅은 여기까지다. FWA 시리즈는 일단 완결나는 걸로 하겠다.