[알고리즘] 그래프 최단경로 알고리즘 비교 (다익스트라, 벨만 포드, 플로이드 워셜)

설명

그래프

그래프는 데이터간에 관계가 복잡한 자료를 표현하기에 좋은 자료입니다.

그래프는 노드(Node, or Vertex)와 간선(Edge, or Link)로 구성되어 있습니다.

노드에는 데이터를 저장하고 간선에는 데이터 사이의 관계를 저장합니다. 
예를 들어 인간관계를 저장한다고 하면 각 사람의 정보를 노드에 저장하고 간선에는 각 사람 사이의 관계 정보를 저장하여 그래프로 표현할 수 있습니다. 지역을 저장한다고 하면 각 지역의 정보를 노드에 저장하고 간선에는 지역 사이의 관계 정보를 저장하여 그래프로 표현할 수 있습니다.

 

그래프 탐색

모든 자료구조에서 탐색 알고리즘은 아주 중요한 역할입니다. 전체게시글 검색, 쇼핑 아이템 검색 그리고 로그인에도 탐색이 필요합니다. 그래프는 순차적인 자료구조가 아니기 때문에 배열과는 탐색 방법이 다릅니다. 그래프에서는 경로 탐색을 위해 DFS, BFS를 사용하고 최단 경로를 구하기 위해서는 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘을 많이 사용합니다.

 

 

다익스트라 알고리즘

• 확인(방문)하지 않았던 노드 중 가장 경로가 짧은 노드부터 간선을 따라 경로를 갱신.
• 시작점으로부터 최단 경로로부터 계속해서 갱신하기 때문에 DP(Dynamic Programming)와 같은 양상을 가짐.
• 큐(우선순위 큐(Heap))를 이용하여 구현

 

벨만 포드 알고리즘

• 노드의 수(노드 개수-1)만큼 모든 간선을 따라 경로를 갱신.
• 최단 경로의 간선 개수는 (노드 개수-1) 이므로 (노드 개수-1)만큼의 반복에서 최단 경로를 찾을 수 있음을 보장.
• 음의 순환을 파악할 수 있다. (음의 순환 : 순환이 간선을 따라서 점점 경로가 짧아지며 최단 경로가 음의 무한대를 가지는 순환을 경로 내부에 가지는 구조)
• 특별한 자료구조 없이 배열로 구현

 

플로이드 워셜 알고리즘

• 경로의 중간 노드를 두어 모든 경로를 갱신.
• A→B 경로를 중간에 C를 두어 A→C→B 경로와 비교하여 모든 노드를 중간 노드로 두며 최단 경로를 찾을 수 있음을 보장.
• 모든 노드의 최단 경로를 구할 수 있다.
• 특별한 자료구조 없이 배열로 구현

 

 

비교

시간복잡도에서 V는 Vertex 수, E는 Edge 수를 의미.

다익스트라 알고리즘

• 시간복잡도 \(O(VlogE)\)
• 그래프의 간선이 음수의 가중치(연결 강도)를 가지면 사용할 수 없다.
• 자료구조 중 큐(or Heap)를 필요로 한다.

 

벨만 포드 알고리즘

• 시간복잡도 \(O(VE)\)
• 그래프의 간선이 음수의 가중치를 가져도 사용할 수 있다. 또한 음의 순환도 감지할 수 있다.

 

플로이드 워셜 알고리즘

• 시간복잡도 \(O(V^3)\)
• 그래프의 간선이 음수의 가중치를 가져도 사용할 수 있다. 또한 음의 순환도 감지할 수 있다.