[알고리즘] 플로이드 와샬과 다익스트라 알고리즘

 

들어가며

오늘은 그래프 자료구조에서 자주 사용되는 알고리즘인 플로이드 와샬과 다익스트라에 대해서 알아보도록 하겠다.필자가 느꼈을 때, 유독 그래프와 관련된 알고리즘의 종류가 많은 것 같다.이는 그래프라는 자료구조가 범용성이 넓기 때문이라고 생각한다.트리 등과 같이 다양한 형태로 사용할 수 있기에 그에 맞게 종류가 많은 듯하다.따라서, 그래프에 대해서 개념을 잘 잡아야할 필요가 있으며, 그래프의 원리로 탄생한 대표적인 알고리즘 역시 이해하는 것이 매우 중요하다.

어느 상황에서 사용할까

기술 블로그를 작성하면서 항상 하는 말이 있다.이거 왜 쓰는 가?무엇이든지 필요없는 것은 사용되지 않기 마련이다.그리고 둘 중에서 하나가 압도적으로 성능이 좋더라면 굳이 두 개를 동시에 배울 필요는 없을 것이다.플로이드 와샬과 다익스트라 알고리즘은 모두 간선간의 최단 거리를 구한다는 목적은 동일하지만 엄연히 다르다.각 장단점이 분명하며, 각자 사용할 수 있는 상황과 동작 방식이 다르다.

다익스트라 알고리즘

우선 다익스트라 알고리즘에 대해서 알아보자. (이 형님은 어딜가나 있다. 정말 대단하신 분이다. 컴공생들의 원수이기도 한 .. 물리로 치면 뉴턴과도 같으신 분 ^^)

시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.

모든 정점과 정점 사이의 최단 경로는 찾을 수 없다는 것이 단점이다.

또한, 그래프에 음의 가중치가 있다면 사용할 수 없다.

왜 그럴까?이는 동작 방식을 통해서 알 수가 있다.

 

동작 방식

1. 시작 정점에서부터 각 정점까지의 최단 거리를 저장하는 배열을 초기화한다.
2. 시작 정점을 기준으로 인접한 정점들을 탐색하면서 최단 거리를 업데이트한다.
3. 방문하지 않은 정점 중에서 최단 거리가 가장 짧은 정점을 선택하여 방문한다.
4. 선택된 정점을 기준으로 다시 인접한 정점들의 최단 거리를 업데이트한다.
5. 위 과정을 모든 정점을 방문할 때까지 반복한다.

다익스트라 알고리즘의 음의 그래프에서 사용할 수 없는 이유

동작 방식에서 알 수 있듯이, 다익스트라 알고리즘은 기존 거리보다 짧으면 최단 거리 값을 업데이트한다.

현재까지 발견된 최단 거리를 업데이트하는 과정에서 항상 가장 짧은 경로를 선택하는 것을 전제로 하기 때문이다.(이를 보장하기 위해서 탄생하였다.)

하지만 음의 가중치가 있으면 해당 정점을 거치는 경로가 더 짧아질 수 있으므로 알고리즘이 올바른 결과를 보장할 수 없는 것이 첫번째 이유이다.
그리고 음의 가중치가 있는 그래프에서는 음의 사이클이 존재할 수 있다.

음의 사이클을 무한으로 돌면 돌수록 해당 거리가 계속해서 최단 거리가 되기 때문에 무한 루프에 빠질 수 있다는 것이 두번째 이유이다.

다익스트라 알고리즘은 한 번 방문한 정점은 더 이상 고려하지 않도록 하기 위해 방문한 정점의 최단 거리를 업데이트하는 과정을 거치는데, 음의 사이클이 있으면 계속해서 최단 거리가 갱신되기 때문에 알고리즘이 종료되지 않고 무한루프에 빠지게 된다.

하지만 한 번 방문한 정점을 더 이상 방문하지 않아도 되기 때문에 속도가 빠르다는 막강한 장점이 있다.

플로이드-와샬 알고리즘

플로이드-와샬 알고리즘은 모든 정점 쌍 사이의 최단 경로를 찾는 알고리즘이다.

다익스트라와 달리 음의 가중치를 가진 간선이 있어도 사용할 수 있다는 특징이 있다.

동작 방식은 아래와 같다.

 

동작 방식

1. 최단 거리를 저장하는 2차원 배열을 초기화한다.
2. 중간 정점을 거쳐가는 경우와 거치지 않는 경우를 고려하여 최단 거리를 업데이트한다.
3. 모든 정점 쌍에 대해 최단 거리를 구한다.

플로이드-와샬 알고리즘은 다익스트라 알고리즘과 달리 음의 가중치를 가진 그래프에서도 사용할 수 있으며, 모든 정점 쌍의 최단 거리를 한 번에 구할 수 있는 장점이 있다.

또한, 코드 구현이 직관적이기 때문에 어렵지 않고 한눈에 알아볼 수 있다.

하지만, 모든 정점 간의 경우를 모두 살펴야하기 때문에 속도가 느리다는 취약한 단점이 있다.