Shortest Path Algorithm

✔️ 최단 경로 문제(Shortest Path Problem)

◾️ 가중치 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제

◾️ 가중치가 없는 그래프에서의 최단 경로는 BFS로 찾을 수 있다.

---

✔️ 다익스트라(Dijkstra)의 최단 경로 알고리즘

◾ 단일 시작점 최단 경로 알고리즘이다.

◾ 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산한다. 

◾ 다익스트라 알고리즘은 BFS처럼 시작점에서 가까운 순서대로 정점을 방문한다.

1️⃣ 다익스트라 알고리즘 : 우선순위 큐를 사용하는 BFS 

📋 우선순위 큐

◾ 우선순위 큐에 정점의 번호와 지금까지 찾아낸 해당 정점까지의 최단 거리를 쌍으로 넣는다.

◾ 우선순위 큐는 정점까지의 최단 거리를 기준으로 정점을 배열함으로써, 아직 방문하지 않은 정점 중 시작점으로부터의 거리가 가장 가까운 점을 찾는 과정을 간단하게 해준다. 

📋 동작 과정

◾ 우선순위 큐를 사용한다는 점을 제외하면 다익스트라 알고리즘의 구조는 너비 우선 탐색과 비슷하다.

1. 각 정점까지의 최단 거리를 저장하는 배열 dist[] 를 유지한다.

2. 정점을 방문할 때마다 인접한 정점을 모두 검사한다.

3. 간선 (u,v)를 검사했는데 v가 아직 방문하지 않은 정점이라면, u까지의 최단거리에 (u,v)의 가중치를 더해 v까지의 경로 길이를 찾는다.

4. 이때 그 경로가 지금까지 우리가 찾은 최단 거리라면 dist[v]를 갱신하고 (dist[v], v)를 큐에 넣는다. 

📋 유의점

◾ 각 정점까지의 최단 경로가 갱신되면, 해당 정점은 우선순위 큐로 들어간다.

◾ 이렇게 되면 최단 경로가 아닌 (가중치, 정점) 쌍이 이미 우선순위 큐에 존재할 수 있는데, 나중에 큐에서 해당 쌍이 꺼내지면 무시한다. 

 

⏰ 시간복잡도

◾ 각 정점마다 인접한 간선들을 모두 검사하는 시간 + 우선순위 큐에 원소를 넣고 삭제하는 시간

◾ 각 정점은 정확히 한 번씩 방문되고, 따라서 모든 간선은 한 번씩 검사된다. 따라서 간선을 검사하는 시간은 O(|E|) 시간이 걸린다.

◾ 우선순위 큐에 원소를 넣고 삭제하는 시간을 알기 위해서는 우선순위 큐의 크기를 알아야한다.

◾ 최악의 시나리오는 모든 간선이 검사될때마다 dist[]가 갱신되고 우선순위 큐에 정점의 번호가 추가되는 경우다. 이때 우선순위 큐에 추가 되는 원소의 수는 최대 O(|E|)가 된다. 따라서 우선순위 큐에 원소를 추가하거나 삭제하는 작업은 O(log|E|)이 되고, O(|E|)개의 원소에 대해서 작업해야하므로 O(|E|log|E|)가 된다.

◾ 따라서 전체 시간복잡도는 O(|E| + |E|log|E|) = O(|E|log|E|)가 된다. 대개의 경우 그래프에서 간선의 개수 |E|는 |V|^2보다 작기 때문에 O(log|E|) = O(log|V|)라고 볼 수 있다. 따라서 시간 복잡도는 O(|E|log|V|)이다.

💾 소스코드 

#include<vector>
#include<queue>
using namespace std;

// 정점의 개수
int V;

// 그래프의 인접 리스트 (연결된 정점 번호, 간선 가중치) 쌍을 담는다.
vector<pair<int, int>> adj[100];

vector<int> dijkstra(int src) {
	vector<int> dist(V, 0x7fffffff); // 각 정점의 최단 경로를 담는 dist 배열은 초기에 최대값으로 셋팅한다. 
	dist[src] = 0;
	priority_queue<pair<int, int>> pq; // (해당 정점에 대한 현재까지 구한 최단경로, 정점 번호)
	pq.push({ 0, src });

	while (!pq.empty()) {
		int cost = -pq.top().first;
		int here = pq.top().second;
		pq.pop();

		// 만약 지금 꺼낸 것보다 더 짧은 경로를 알고 있다면, 지금꺼낸 것을 무시한다.
		if (dist[here] < cost) continue;

		//인접한 정점들을 모두 검사한다.
		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first; // 인접 정점 번호
			int nextDist = cost + adj[here][i].second; // 해당 인접 정점까지의 거리 

			if (dist[there] > nextDist) { // 인접 정점에 대한 최단 경로라면,
				dist[there] = nextDist; // dist 배열에 업데이트
				pq.push({ -nextDist, there }); // (해당 정점에 대한 새로운 최단경로, 정점 번호)
			}
		}
	}

	return dist;
}

 

2️⃣ 다익스트라 알고리즘 : 우선순위 큐를 사용하지 않는 다익스트라 알고리즘

(추후 작성예정)

---

✔️ 벨만-포드(Bellman-Ford)의 최단 경로 알고리즘

◾ 단일 시작점 최단 경로 알고리즘

◾ 음수 간선이 있는 그래프에 대해 최단 경로를 찾을 수 있다. 

 

(추후 작성예정)

---

✔️ 플로이드(Floyd)의 최단 경로 알고리즘 

◾ 모든 정점 쌍간의 최단 경로를 구하는 알고리즘

 

(추후 작성예정)