최단거리 문제에 대한 고찰

최단 경로 문제는 가중치 없는 그래프에서는 보통 두 정점을 잇는 가장 적은 간선의 개수를 뜻합니다.

반대로 가중치가 있는 그래프에서는 두 정점을 잇는 간선들의 가중치의 합 중 최소 가중치 합을 의미합니다.

 

알고리즘 공부하고, 코딩테스트 문제를 접하다보면? 가중치 없는 그래프(unweighted graph)인 경우 BFS를 사용하고, 가중치가 0과 1이 존재할 때 역시 BFS를 사용한다고 생각합니다.

그리고 가중치가 여러 개가 존재한다면 다익스트라 알고리즘을 사용하라고 합니다.

이번 주제에선, 왜 최단거리에선 DFS를 사용하지 않고 BFS를 사용하는 지? 와

간선이 0과 1일 때는 다익스트라 알고리즘을 사용하기보단, 0-1 알고리즘을 사용하는 지? 에대한 설명을 드릴 생각입니다.

 

최단 경로를 탐색할 때 DFS를 사용하지 않는 이유와 BFS에 대하여,

1. 최단 경로를 검색할 때, 재귀적인 방법으로 DFS를 구현했을 때, 트리 형태라는 확증이 있어야합니다.

> 만약 그래프의 경우라면, 내가 최종적으로 방문한 경로가 최단경로인 지 확신할 수 없기 때문입니다.

nodeA로 갈 수 있는 이전 정점 NodeB와 NodeC가 있다고 하면, NodeB와 NodeC로 갈 때, 정답이 달라질 수 있다는 점입니다.
그렇지만, 모든 노드를 다 탐색해서 각각의 노드를 시작점으로 탐색하여 최단 경로를 찾아보겠다는 생각을 할 수 있지만?
굉장히 비효율적일 수 밖에 없습니다.
모든 노드가 시작점으로 경로가 되어야하고, 모든 도착점 역시 시작점으로 고려되어야 하기 때문입니다.
따라서 이러한 경우에는 O([N의개수]²) 이기 때문에 굉장히 비효율적이라고 볼 수 있습니다.
이 외에도 stack을 사용하는 DFS에 비해, BFS는 queue나 deque를 사용하므로, 비교적 stackoverflow 문제에서 자유롭게 공간을 활용할 수 있어, 넓은 범위를 탐색할 수 있는 이점이 있습니다.

 

2. 가중치가 있는 그래프에서 DFS와 BFS를 사용하지 않는 이유

 

BFS

우리가 가중치가 없는 그래프인 경우 BFS를 사용한다는 건 잘 알고 계실 겁니다.

이와 함께 간선에 가중치가 존재한다면, BFS를 사용할 수 없다는 것도 익히 알려진 사실입니다.

👇 BFS가 최단거리를 보장하는 이유

---

BFS는 자신과 바로 연결되어 있는 노드들을 큐에 넣는다. 그리고 큐는 FIFO에 따라서 가장 먼저 들어온 것들을 먼저 처리한다. 이 두가지 특성이 결합되어 시작지점으로부터 간선의 수가 작은 곳부터 먼저 처리되게 된다. 따라서 간선 2개로 도달할 수 있는 노드가 간선 1개로 도달할 수 있는 노드보다 큐에 먼저 들어오는 일은 발생하지 않으므로 최단거리를 보장할 수 있다.

---

단순히 depth로만 최단 거리가 정해지는 것이 아니기 때문에, 같은 depth에 있는 노드끼리 이동하는 것은 고려하지 않습니다.

예를 들어,

nodeA가 (nodeB, nodeC)랑 연결 되어 있고, nodeB가 nodeC와 서로 연결되어 있다고 생각을하면

A는 depth가 1, B,C는 depth가 2로 생각하면 된다. 그렇게 되면, A-B가 가중치6, A-C 가중치2, B-C가 가중치 3이라고 가정할 때,

depth 기준과 weight 기준으로 최단거리가 달라지게 됩니다. 아래 그림을 보고 생각하면 이해하기 쉬울 것입니다.

DFS

가중치가 존재할 때, DFS를 사용할 수는 없을까?

물론 DFS를 사용하여, 모든 간선을 전부 돌아보게하면? 가중치를 전체 고려하여 최단거리를 찾을 수 있습니다.

하지만, 이러한 경우 효율성이 지나치게 떨어집니다.

 

탐색해야하는 경로가 정점의 수에 따라 팩토리얼로 증가하게 됩니다.

Fully connected graph를 가정한다면, 정점의 수가 n개일 때 탐색해야하는 경로의 수는 n! 입니다.

 

3. 가중치가 있는 그래프에서 다익스트라 알고리즘을 쓰는 이유는?

가중치가 있는 그래프에서 BFS를 사용할 수 없는 이유는 BFS가 Greedy한 알고리즘이 아니기 때문입니다.

이와 달리, 다익스트라 알고리즘은 Greedy 합니다.

그리디한 이유는 최소 거리에 최소 거리를 붙이면 최소 거리가 될 것이라는 논리가 함축 되어 있기 때문입니다.

그래서 우리는 다익스트라 알고리즘이 최소 거리를 보증한다는 것을 귀류법으로 증명할 수 있습니다.

 

👇 그리디한 알고리즘이란?

---

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란

"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법입니다.

---

👇 귀류법 증명

---

• 가설: 이미 선택된 노드는 최단 거리가 갱신되지 않는다. 즉, 다익스트라 알고리즘으로 선택된 노드는 최종 최소 비용이다.
• 가. 이미 선택된 노드는 앞으로 선택되는 노드에 의해서 최단 거리가 갱신이 된다라고 가정한다. 즉, 이후 선택하는 노드를 거쳐 들어오는 더 짧은 최단 경로가 존재한다.
• 나. 만일 그러한 노드가 존재한다면, 해당 노드는 적어도 한 번 다익스트라 알고리즘을 이용해 거쳐온 노드 외의 노드를 지나야만 한다. 다익스트라 알고리즘으로 선택되어진 모든 노드만을 거쳐서 지나온다면, 해당 노드는 다익스트라 알고리즘으로 선택된 노드의 최소 비용을 갱신할 수 없기 때문이다.
• 다. 위의 (가)와 (나) 단계는 모순이다. 다익스트라 알고리즘은 분명 매번 최소 비용을 갖는 노드만을 선택한다고 하였는데, 그것보다 더 짧은 비용을 갖는 노드가 존재한다고하면 당연히 모순이다.
• 결론: 초기에 설정한 가정(이미 선택된 노드는 앞으로 선택되는 정점에 의해서 최단 거리가 갱신이 된다)은 모순이다. 즉, 귀류 가정이 모순이므로, 본 명제는 참이다.

---

 

다익스트라 알고리즘은 우선순위 큐를 이용하여, 현재 시점에서 가장 거리가 짧은 간선을 선택하게 됩니다.

우선순위 큐를 구현하기 위해서 최소 이진힙을 주로 이용합니다.

또한, 가중치가 음수인 경우에는 사용할 수 없습니다.

그 이유는 가중치가 음수라면 최소 비용을 매 번 갖는 노드보다 더 짧은 비용을 갖는 노드가 존재할 수 있기 때문입니다.

가중치가 0보다 크다면, 간선을 통과하는 모든 경우에 비용이 증가하거나 같을 수밖에 없습니다.

하지만,

음수라면 간선을 통과할 때 무조건 감소하게 됩니다...

따라서, 음수 가중치를 이용할 때는 벨만 포드 알고리즘을 사용해야 합니다.

 

 

4. 가중치가 0과 1만 존재하는 그래프에서 BFS를 쓰는 이유는?

어느 임의의 그래프에서 간선 (u, v)를 지닌다고 가정할 때,

가중치가 0과 1만 존재하므로, 우리는 간선(u, v)를 지날 때 노드 u와 v에 대해 다음의 사항을 고려할 수 있습니다.

1. 가중치가 0이라는 것은 v는 u와 같은 레벨이다.
2. 가중치가 1이라는 것은 v는 u의 1레벨 아래이다.

또한 우리는 이미 BFS 실행 중에는 큐에 있는 정점은 최대 2가지의 레벨로만 이루어져 있는것을 알 수 있습니다.

그러므로 만약 우리가 u정점에 있다면, 큐는 레벨이 L[u] 또는 L[u]+1인 정점만 들어있습니다.
그리고, 간선(u, v)에 대해, L[v]는 L[u] 또는 L[u]+1입니다.
그러므로, v정점이 u에 의해 최단거리가 단축되었고, u와 같은 레벨이라면 큐의 앞 부분에 v를 삽입합니다.
반대의 경우에는 큐 뒷 부분에 삽입합니다.
이 행위는 BFS가 제대로 작동하기 위해 큐가 정렬된 상태를 유지하는 것을 도와줍니다.

하지만, 일반적인 큐 구조를 사용하면 삽입과 정렬된 상태를 유지하는 것을 O(1)만에 수행하지 못합니다.
우선순위큐(Priority Queue)는 정렬된 상태를 유지하는데 O(logN)을 소모합니다.

일반적인 큐의 문제는 다음 3가지 기능을 수행하는데 도움이 되는 메소드가 없다는 것입니다.

1. 다음 정점 추출하기(BFS를 위해 정점 추출)
2. 가장 앞쪽에 삽입하기(같은 레벨의 정점 삽입 )
3. 가장 뒤쪽에 삽입하기(다른 레벨의 정점 삽입 )

다행스러운건, 덱(Deque, Double Ended Queue)이라는 자료구조가 모든 기능을 제공합니다.

 

    for all v in verticces:
        dist[v] = inf
    dist[start] <- 0
    deque d
    d.push_front(start)

    while d.empty() == false:
        vertex = get front element and pop as in BFS
        for all edges e of form(vertex, u):
            if travelling e relaxes distance to u:
                relax dist[u]
                if e.weight = 1:
                    d.push_back(u)
                else:
                    d.push_front(u)

시간복잡도는 선형 시간이고, 다익스트라보다 훨씬 효율적인 O(E + V)입니다.