[Algorithm] 최단 경로 탐색 알고리즘

최단 경로 알고리즘

그래프 상황에서 vertex 간의 최단 경로를 구하는 알고리즘이다.

 

 

백준 1753번 최단경로 문제

 

문제는 위와 같이 아예 그래프로 문제 상황이 주어지거나,

 

백준 1865번 웜홀 문제

혹은 위와 같이 '경로'로서 문제 상황이 주어진다.

 

문제를 graph, vertex, edge로 표현하여 풀면 된다.

 

단일 출발 최단 경로

특정 하나의 노드에서 다른 모든 노드까지의 최단 경로를 구하는 문제이다.

 

백준 11657번 타임머신 문제

 

1. 다익스트라 알고리즘

음수 가중치 미포함 경우에만 사용 가능하다.

1. 방문하지 않은 정점 중, 거리가 최소인(cost가 낮은) 정점을 방문한다. 
2. 정점을 방문 처리하고, 최단 거리를 확정한다.
3. 현재 처리 중인 (최단 거리가 확정된) 노드를 거쳐서 다른 노드로 가는 비용을 계산하고 갱신한다. 

특징

• 거리가 최소인 정점을 찾는 과정에서 Heap 혹은 Priority Queue가 이용된다.
• 각 노드에 대한 현재까지의 최단 거리 정보를 1차원 리스트에 저장하여 리스트를 계속 갱신한다.
• 매번 현재 처리하고 있는 노드를 기준으로 주변을 확인하며, 현재 처리 중인 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면 해당 경로를 제일 짧은 경로로 판단한다.

https://subbni.tistory.com/63

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

 

2. 벨만 - 포드 알고리즘

음수 가중치를 포함하는 경우에도 사용 가능하다.

모든 경우의 수를 고려하는 동적 계획법을 사용한다.

따라서 다익스트라보다 시간 복잡도가 높다.

• 모든 노드가 한 번씩 출발점이 되어 다른 모든 노드까지의 최소 거리를 구한다.

예를 들어 현재 출발점인 노드가 v, 출발점 노드가 아닌 다른 노드를 s라고 할 때,

dist[s] 와 dist[v] + dist[v -> s] (v까지의 거리 + v에서 s까지의 거리)를 비교한다.

 

모든 쌍들의 최단 경로

그래프에 포함된 모든 vertex 쌍들에 대한 최단 경로를 구하는 문제이다.

백준 10159번 저울 문제

1. 플로이드 - 워셜 알고리즘

음수 가중치를 포함하는 경우에도 사용할 수 있다.

동적 계획법을 사용한다.

- 2차원 배열 사용 : 모든 노드 간의 최단 거리를 구하며, 동적 계획법을 사용한다.

- 3중 for문 : 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다.