최단 경로 알고리즘(Shortest Path)

오늘은 최단 경로 알고리즘에 대해서 간단하게 개요를 정리하자.

최단 경로란?

 

그래프 상에서 가장 짧은 경로를 찾는 경로, 가중치 그래프에서는 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제다.

그런데, 최단 경로라고 해도 문제마다 다르다. 어떤 경우들이 있을까?

 

단일 출발 최단 경로 : 어떤 하나의 정점에서 출발하여 나머지 모든 정점까지의 최단 경로

단일 도착 최단 경로 : 모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로 (뒤집어서 생각하면 단일 출발 최단 경로다)

단일 쌍 최단 경로 : 모든 정점에서 모든 정점까지의 최단 경로

최단 경로 알고리즘

 

최단 경로 문제가 나오게 되면 이를 해결할 알고리즘들이 있다.

 

BFS(완전 탐색)

가중치가 없거나 가중치가 모두 동일한 경우(미로 탐색 문제)에서는 최단 경로를 구할 수 있게 된다.

(1, 1) -> (N, M)

# 특이하게도, 0의 가중치와 1의 가중치가 동시에 존재하는 0-1 BFS도 있다.

이럴 때는 0의 가중치를 큐의 앞부분에 우선적으로 배치하여야 한다.

 

다익스트라 알고리즘

음이 아닌 가중치의 그래프에서만 사용할 수 있는 알고리즘.

어떤 하나의 정점에서 나머지 모든 정점까지의 최단 경로를 구할 때 사용한다.

 

벨만 포드 알고리즘

음인 가중치도 사용할 수 있는 알고리즘

나머지는 다익스트라 알고리즘과 비슷하다.

 

플로이드 워셜 알고리즘

모든 정점 사이의 최단 경로를 모두 구하는 알고리즘

3중 포문으로 구현이 쉽다.

 

여러 알고리즘을 알았으니, 제일 좋은 공부법은 알고리즘 틀을 배우고 빠르게 여러 문제들을 풀면서 복습하는 느낌으로 공부하자.