최단거리 알고리즘을 아라보자

유명한 최단거리 알고리즘은 아래의 3가지가 있다.

다익스트라

• 그래프의 최단 경로 구하는 알고리즘
• 하나의 정점에서 출발하는 최단 거리를 구함(출발지만 정함)
• 음수 가중치 없어야 함
• 인접 행렬로 표현된 그래프의 경우 시간 복잡도 O(n^2)
• 우선순위 큐 사용하여 시간 복잡도 O(mlog n)까지 낮출 수 있음 → 개선된 다익스트라 알고리즘
• 탐욕법과 동적 계획법 사용

 

출발지를 하나 정하고 최소 비용을 구하는 부분이 벨만-포드와 같다.

다익스트라 알고리즘의 순서

1. 아직 방문하지 않은 정점중 출발로 부터 가장 거리가 짧은 정점을 방문
2. 해당 정점을 거쳐갈 수 있는 정점의 거리가 이전 기록한 값보다 적으면 갱신

 

벨만 포드

• 그래프의 최단 경로를 구한다.
• 하나의 정점에서 출발하는 최단 거리를 구함(출발지만 구함)
• 음수 가중치 허용
• O(nm)
•  

다익스트라의 다른점은 다음과 같다.

 

	다익스트라	벨만-포드
음수 가중치	X	O
음수 사이클	X	X
시간복잡도	O(mlog n)	O(mn)

 

 

벨만 포드는 다익스트라의 한계를 보완한다.

다익스트라는 간선이 음수 사이클이 생기면 최단 경로를 구할 수 없지만

벨만포드는 가능하다.

기본적으로 다익스트라와 동일하지만 핵심 차이점은 간선의 가중치가 음일 때도 최소 비용을 구할 수 있다. 다만 시간복잡도가 늘어나기 때문에 가중치가 모두 양수일 경우 다익스트라를 사용하는 것이 좋다. 시간 복잡도가 늘어나는 이유는 그리디하게 최소 비용 경로를 찾아가는 다익스트라와 달리, 벨만 포드는 모든 경우의 수를 고려하는 동적 계획법이 사용되기 때문이다.

플로이드-워셜

• 그래프의 최단 경로를 구함
• 모든 정점에서 모든 정점까지 최단거리를 구함
• 음수 사이클이 없어야 함
• O(n^3)

플로이드 워셜은 모든 노드간의 최단거리를 구한다.
한 노드에서 다른 모든 노드까지의 거리를 구하는 다익스트라와는 대조된다.