그래프 경로 알고리즘

그래프에서 경로를 찾는데 많이 사용되는 알고리즘이나 방법들이 있다.
DFS와 BFS만으로 해결이 될줄 알았는데 큰 오산이었다.
그래서 오늘 알아볼 내용은 다익스트라와 플로이드워셜이다.
 
두 알고리즘 모두 최단 경로를 찾지만 다익스트라는 하나의 정점에서 다른 모든 정점으로의 최단 경로를 찾는 알고리즘이고 플로이드 워셜의 경우 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다.
 
위 두 알고리즘 모두 다이나믹 프로그래밍적 특징을 가지고 있다.
 

 
가령 위 그림과 같이 1에서 갈 수 있는 노드의 최단거리는 각각 1, 3이지만
1에서 2로 1만큼가고 2에서 3으로 1만큼 간다면 거리는 2로 1에서 3으로 바로 갔을때의 거리 3보다 작게된다.
즉, 어떤 점에서 어떤 점까지 최단 거리는 여러개의 최단 거리로 이루어져 있을 수 있기 때문에 DP문제라고 볼 수 있는 것이다.
다만, 주의해야할점은 음의 거리가 있어서는 알고리즘들이 제대로 동작하지 않으며 특히나 음수로 이루어진 사이클이 있는 경우 무한루프에 빠지게 된다. 입력 조건을 잘 보고 이 알고리즘을 선택하도록하자.
 
다익스트라부터 살펴보자. 코드로 구현하는 과정은 다음과 같다.
 
1. start 점에서 다른 모든 점까지의 거리를 배열에 저장한다. ( 간선 정보가 없다면 가능한 최대치로 저장 )
2. 현재 배열에서 방문하지 않은 가장 작은 거리의 노드를 기준으로 배열을 업데이트한다.
 

// 노드 수, 간선 정보 수
int n, m;
int MAX = 10000000;

bool visited[n+1];
int distance[n+1];

// 특정 노드에서부터 다른 노드까지의 거리 정보
int dis[n][n] = {};

int shoretest_node()
{
	int min = MAX;
    int index = 0;
    // 배열 내에서 방문하지 않은 가장 짧은 거리의 노드 찾기
    for(int i=0;i<n;i++)
    {
    	if (distance[i] < min && !visited[i])
        {
        	min = distance[i];
            index = i;
        }
    }
    return index;
}

void dijkstra(int start)
{
	// 1번 과정
	for(int i=0;i<n;i++)
    {
    	distance[i] = dis[start][i]; // start 에서 i 번째 노드로의 거리
    }
    visited[start] = true;
    for(int i = 0; i < n - 1; i++)
    {
    	// 2번 과정
        // 노드 방문하면서 업데이트 시작
    	int now = shoretest_node();
        visited[now] = true;
        for(int j=0;j<n;j++)
        {
        	if (!visited[j] && distance[now] + dis[now][j] < distance[j])
            {
            	// 아직 방문하지 않은 노드 중
                // 현재 최단 거리보다 더 짧은 경로가 있다면 변경
            	distance[j] = distance[now] + dis[now][j];
            }
        }
    }
}

int main()
{

	// 정보 초기화
    for(int i=0;i<n;i++)
    {
		distance[i] = MAX;
    }
 
 	// 간선 정보 입력
    for(int i=0;i<m;i++)
    {
    	int from, to, dis;
        cin >> from >> to >> dis;
        dis[from - 1][to - 1] = dis;
    }
    
    dijkstra(0);

	return 0;
}

 
하지만 이 방법은 거의 노드 수 n 만큼 돌면서 크기 n 의 배열 을 검사해 가장 작은 거리를 찾아야하기 때문에 O(N^2) 의 시간이 걸린다. 결국 거리가 우선순위로 작용하기 때문에 우선순위큐를 사용하여 훨씬 시간을 아낄 수 있다.
 

// 인접리스트 형식으로 정보 저장
vector<pair<int, int>> node[n];

void dijkstra()
{
	// 우선 순위 큐 작은 값을 기준으로 정렬되어 저장
    priority_queue<pair<int, int>> que;
    que.push(make_pair(0, start));
    distance[start - 1] = 0;
 
    while (!que.empty())
    {
    	// 우선순위 큐는 front가 아니라 top 사용
        int cost = -que.top().first;
        int now = que.top().second;
        que.pop();
        
        // 한번 방문한 노드는 두번 방문하지 않음
        if (distance[now]<cost) continue;
 
        for (int i = 0; i < node[now].size(); i++)
        {
            int next = node[now][i].first;
            int ncost = node[now][i].second;
 
 			// 연결된 노드로의 이동이 거리가 더 적다면 값을 바꾸고 큐에 넣어줌
            if (distance[next] > cost + ncost)
            {
                distance[next] = cost + ncost;
                que.push(make_pair(-distance[next], next));
            }
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        if (distance[i] == MAX) distance[i] = -1;
        cout << distance[i] << endl;
    }
}

 
 
이렇게 우선순위큐를 이용해서 앞선 코드의 shortest_node 함수를 없애버린 셈이 되었다.
모든 정점들에 대해서 우선순위큐로 만드는데 걸리는 시간이 O(logN)이고 이렇게 만들어진 큐에서 나온 노드의  인접한 간선을 모두 확인해봐야하기 때문에 간선의 수 M이 곱해져 O(M*logN)의 시간이 걸리게 되는 것이다.
 
다음 알고리즘을 살펴보자.
 
플로이드 워셜알고리즘의 경우 모든 정점에서 모든 정점까지의 최단거리를 구한다고 했다.
그렇다면 문득 그런 생각이 들지 않는가 ? 다익스트라가 1차원 형태의 배열을 사용했으니 플로이드 워셜은 2차원 배열 형태를 사용하지 않을까 ?
 
맞다. 아까 위에서 보았던 그림을 토대로 설명하면

	1	2	3
1	0	1	3
2	1	0	1
3	3	1	0

 
각 행열은 From과 To의 관계를 갖는다.
자기 자신에게 갈 때는 비용이 들지 않으며 만약 1과 연결되지 않고 3만 연결된 4번 노드가 있다면 해당 표에서 1과 4의 관계는 무한대로 표현된다. 그럼 이제 이 표를 어떻게 업데이트 해야될까 ?
다익스트라를 설명하면서 보았던대로 1 -> 3 까지는 3으로 거리가 잡혀있는 상태이다. 하지만 우리는 최단 거리가 1 -> 2 -> 3 이라는 것을 안다. 그럼 이는 node[1][3] > node[1][2] + node[2][3] 으로 설명할 수 있다. 이제 조금 뭔가 보이지 않는가 ?
 
어떤 노드 I 에서 다른 어떤 노드 J 로 가는 최단 거리는 Node[I][J] 이거나 또 다른 어떤 노드 K 를 경유해 오는 최단 거리 Node[I][K] + Node[K][J] 라는 것이다. 이제 우리가 해야할 일은 이를 일반적으로 어떻게 표현하는가이다.
이를 코드로 구현해보자.
 
1. 2차원 배열 형태로 모든 노드의 거리 정보를 입력
2. 반복문을 수행하면서 해당 2차원 배열의 최단거리 정보를 업데이트, min(Node[I][J], Node[I][K] + Node[K][J])
 

int n, m;
// 노드 0번부터 n-1번까지 사용 가능
int nodes[n][n] = { 0, };

int MAX = 100000000;

void floyd_warshall() {

    // 거쳐가는 지점 K
    for (int k = 0; k < n; k++)
    {
        // 출발 지점 I
        for (int i = 0; i < n; i++)
        {
            // 도착 지점 J
            for (int j = 0; j < n; j++)
            {
            	// I -> J 로 가는 최단 거리는 
                // 직행이거나 K를 경유하는 것 중 더 작은 것
                nodes[i][j] = min(nodes[i][j], nodes[i][k] + nodes[k][j]);
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << nodes[i][j] << " ";
        }
        cout << endl;
    }
 
}

int main()
{
	for(int i=0;i<n;i++)
    {
    	for(int j=0;j<n;j++)
        {
        	// 자기 자신은 0 그 외에는 모두 MAX로 초기화
        	if (i != j) node[i][j] = MAX;
        }
    }
    
    // m 만큼의 간선 정보 입력
    for(int i=0;i<m;i++)
    {
    	int from, to, distance;
        cin >> from >> to >> distance;
        node[from - 1][to - 1] = distance;
        // 무방향 그래프의 경우 from 과 to 를 바꿔서 한번더 저장
    }
}

 
플로이드 워셜은 이렇게 표현된다.
정점 From에서 To까지 K를 경유해서 가는게 빠른지 그냥 가는게 빠른지 비교해가면서 업데이트하면 되는 것이다.
하지만 이는 N만큼 탐색하는 3중 포문을 가지고 있기 때문에 O(N^3)의 시간을 소요하게 된다. 만약 노드의 수가 너무 큰 문제라면 이 방법은 절대 택하면 안될 것같다.
 

정리하자면,

 

다익스트라는 하나의 정점에서 모든 정점의 최단 거리를 구하는 알고리즘이며 O(M*logN)
플로이드 워셜은 모든 정점에서 다른 모든 정점의 최단 거리를 구하는 알고리즘 O(N^3)

 
 
나는 다익스트라보다 플로이드가 훨씬 이해하기 편했고 인접리스트를 활용해 구현하기도 편했다.
문제를 풀면서 아마 자주 사용하게 될 것 같으니 잘 이해해둘 필요가 있어보인다.