최단거리 개념 및 문제 접근 방법

0. 개요

- 최단 거리 알고리즘은 그래프 탐색 알고리즘 중 하나이다.

- 최단 거리 알고리즘의 종류와 개념 그리고 문제 접근 방법에 대해서 알아보자.

 

1. 최단 거리 개념과 종류

a) 최단 거리의 의미

- 최단 거리 문제에서 최단 거리는 다음 2가지 경우 중 하나에 해당한다.

   → 지나온 간선(edge)의 개수가 가장 적은 경로를 찾는 경우 (가중치가 없는 그래프)

   → 지나온 간선(edge)의 가중치(weight) 합이 가장 작은 경로를 찾는 경우 (가중치가 있는 그래프)

 

 

b) 최단 거리의 종류

- 최단 거리 문제는 기본적으로 시작점과 도착점이 주어진다.

- 시작점과 도착점을 기준으로 최단 경로(간선의 개수 또는 간선 가중치의 합)를 구하는 것이 문제의 핵심이다.

- 시작점과 도착점의 구성 방식에 따라서 다음 4가지 종류로 분류된다.

   → 단일 출발 & 단일 도착(single source & single destination)

   → 단일 출발 & 다수 도착(single source & multi - destination)

   → 다수 출발 & 단일 도착(multi - source & single destination)

   → 다수 출발 & 다수 도착 또는 모든 경로(multi - source & multi - destination, all pairs 문제)

 

 

2. 최단 거리 알고리즘의 종류 및 선택 방법

- 최단 거리 알고리즘은 시작점과 도착점에 따라 사용할 수 있는 알고리즘이 다르다.

- 위에서 언급한 4가지 최단 거리의 종류에 따라 사용할 수 있는 알고리즘을 알아보자. 

 

a) BFS 알고리즘

- 가중치가 없거나 모든 간선의 가중치가 동일한 그래프의 최단 경로 문제에서 사용한다.

 

 

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

- 단일 시작점 또는 단일 도착점 문제에서 사용한다.

- 시작점 또는 도착점 중 하나가 단일 지점이면 사용할 수 있다.

 

 

c) 벨만 포드( Bellman - Ford) 알고리즘

- 다익스트라와 마찬가지로, 단일 출발 또는 단일 도착 문제에서 사용한다.

- 다만, 음의 가중치가 있을 때 사용할 수 있다는 특징이 있다.

 

 

d) 플로이드 - 와샬(Floyd-Warshall) 알고리즘 

- 모든 경로를 탐색하는 다수 출발 & 다수 도착 문제에서 사용한다.

- 플로이드 와샬 알고리즘의 핵심은 '거쳐가는 vertex'를 기준으로 생각한다는 것이다.

- 즉, A → B의 모든 경로 중 거쳐가는 vertex(K)를 기준으로 하여금 A → K의 최단 경로와 K → B의 최단 경로를 구한다.