[알고리즘] BFS와 다익스트라 알고리즘

들어가며

오늘은 그래프에서 최단 경로를 찾는 방법에 대해 정리해보려합니다.

 

정리

상황에 맞는 알고리즘을 잘 정리해둔 것을 보아서 가져와봤습니다.

		단일 node - 단일 node	모든 node쌍
Edge에 weight 없음		Breadth First Search (BFS)	Floyd-Warshall Algorithm
Edge에 weight 있음	음수 weight 있음	Bellman-Ford Algorithm
	음수 weight 없음	Dijkstra Algorithm

출처: https://shnoh.tistory.com/15

 

BFS (너비 우선 탐색)

가장 단순한 형태입니다. weight가 없으니 depth가 곧 거리가 될 것이기 떄문에, 한 depth를 모두 살핀 후 그 다음 depth를 탐색하는 BFS를 통해 문제를 해결할 수 있습니다.

 

방법은 아래와 같이 표현할 수 있습니다.

 

1. 시작 노드를 방문한다. 

2. 그 노드와 연결된 모든 노드 중 방문한 적이 없는 노드를 방문한 후, 방문 표시를 하고, 깊이++한다.

3. 끝 노드를 찾으면 끝내고, 아니면 2를 반복한다.

 

이 방법은 아래 슈도 코드처럼 Queue를 이용하여 구현할 수 있습니다.

 

시작노드 inque

while(큐가 비어있지 않는 동안) {

    [노드, 깊이] = Queue에서 deque

    if (노드 == 찾고자하는 노드) {

        깊이 출력

        종료

    }

    방문 체크

    for (인접리스트에서 해당 노드에 연결된 모든 노드) {

        if(방문한 적 없는 노드라면) {

            Queue에 [다음 노드, 깊이 + 1] enque

        }

    }

}

 

위의 알고리즘은 최악의 경우 모든 노드와 간선을 전부 실핌으로 시간 복잡도는 O(V + E)입니다. V: 노드 E: 간선

 

Dijkstra (다익스트라) 알고리즘

간선에 weight가 존재한다면, 다익스트라를 사용하여 문제를 해결할 수 있습니다.

다익스트라 알고리즘의 핵심은 "최단거리는 여러 개의 최단거리로 이뤄져있다."입니다. 그러므로 다이나닉 프로그래밍이라고 할 수 있습니다. 또한 선택된 노드에서 최단 거리의 다른 노드를 선택하는 과정을 반복함으로 그리디 알고리즘이기도 합니다. 아래의 순서를 보시죠.

 

순서

준비1. 시작노드에서 각 노드로 가는 비용을 기록하는 변수를 만든 후 최대값으로 설정해둔다. 

준비2. 방문 여부를 기록하는 변수를 만든다. 

1. 시작 노드를 선택한다.

2. 선택된 노드를 거쳐서 가는 비용과 기존에 기록된 기록을 비교하여 최단 거리로 갱신한다.

3. 갱신된 비용을 보고 방문하지 않는 노드 중 가장 비용이 저렴한 노드를 선택한다. 

4. 2~3을 반복한다.

5. 모든 노드를 방문 한 후 기록된 비용이, 시작 노드에서 해당 노드로가는 최단거리가됩니다.

 

위의 순서는 Heap 구조를 이용한 Priority Queue와 인접리스트로 표현하여 구할 수 있습니다.

그래프를 표현하는 방법은 인접배열과 인접리스트가 있는데. 한 노드에 연결된 모든 노드들을 매번 찾아야하기 떄문에 인접리스트가 유리합니다. (O(연결된 간선의 수))

또한 매번 방문하지 않는 노드 중 최소비용의 노드를 선택하는 단계에서 일일이 확인하면 O(N^2)이 걸리지만,

Heap을 사용하면 O(NlogN)(heapify를 노드의 수만큼 수행)으로 단축할 수 있습니다.

 

수도 코드

최소비용배열(mc) 생성 //  mc[idx] = 시작 노드부터 idx노드까지의 최소 비용

큐 생성

큐 <- [시작 노드, 0] inque

while(큐가 비어있지 않는 동안) {

    [현재 노드, 최소비용] <- 큐 deque

    if (mc[현재노드] < 최소비용) continue //  중복 방문 방지 목적. mc에 최소비용을 기록하고 이 비용을 inque하기 때문에 mc[현재노드] == 최소비용이어야함. 하지만 최소비용이 더 크다는 의미는 이미 앞에서 이 노드에 방문에서 최소 비용을 계산했다는 뜻. 그러므로 다시 방문하면 중복계산됨!

    for (해당 노드에 연결된  연결노드) {

        새로운비용 <-  mc[현재노드] + 연결노드로 가는 비용

        if(새로운 비용 < mc[연결노드]) {

            mc[연결노드] <- 새로운비용

            큐 <- [연결노드, 새로운비용] enque

        }

    }

}

return 최소비용배열

 

위의 알고리즘의 단점은 음의 가중치를 고려하지 못한다는 것이다. 기본적으로 그리디 알고리즘임으로 현재 상황에서 최선의 선택을 반복해 나간다. 그리고, 최선으로 선택된 노드는 그 값이 고정이 됩니다.

 

예를 들어 아래와 같이 노드와 간선 정보가 주어진 경우,

A -> B : 10

A -> C : 4

B -> C : -100

 

A에서 시작했을 때, 다익스트라 알리즘에 의해 최선으로 C를 선택하게 되고, A에서 C로 가는 최단거리는 4로 고정됩니다.

하지만, 음수의 가중치가 있다면 결과가 달라져야합니다.

 

음수의 가중치가 있다면, 벨만 포드 알고리즘을 사용해야하는데, 다음 글에서 다루겠습니다.

 

나가며

멋진 선생님들께서 많은 연구를 통해 만들어 놓으신 알고리즘들을 많이 알고, 적절한 곳에 적절한 알고리즘을 사용하는 것이 참 중요하겠다라는 생각을 많이하게된 것 같습니다. 다음은 벨만 포드 알고리즘으로 만나요!

 

 

참조

https://shnoh.tistory.com/15

https://kangworld.tistory.com/76