[Algorithm] 다익스트라

최단 경로 (BFS)

- 그래프에 가중치가 서로 같은 경우

최단 거리 (Dijkstra)

- 그래프에 가중치 같이 포함, 정점 A 에서 다른 N 개의 정점에 대한 최소 비용을 구함

 

가중치가 있는 그래프에서 최소 비용 구하기

BFS와 매우 유사하지만, Queue를 사용하는 것이 아닌, PriorityQueue를 통해 인접 정점이 아닌 거리가 제일 짧은 간선을 뽑아낸다.

 

 

 

Dijkstra Algorithm 

시작정점 : 0

 

- 각 순간 마다 가장 작은 비용을 선택하면서, 정답 배열과 비교

파란색: Priority Queue

주황색: 정답배열

 

 

Code

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct Edge {
	int num;
	int cost;
    
    //연산자 오버로딩
	bool operator<(Edge right) const {
		if (cost < right.cost) return false;
		if (cost > right.cost) return true;
		return false;
	}
};
vector<struct Edge> alis[10];
int N, M;

void dijkstra(int node)
{
	//1. priority_queue 준비
	priority_queue<struct Edge> pq;

	//2. 정답 배열 만들기: 정답 배열을 INT_MAX 값으로 초기화
	int dist[100] = { 0, };
	for (int i = 0; i < 100; ++i)
	{
		dist[i] = 2134567890;
	}

	//3. 시작 노드 등록
	dist[node] = 0;
	pq.push({ node, 0 });


	while (!pq.empty())
	{
		//4. 큐 맨 앞 노드 확인 및 추출
		Edge now = pq.top();
		pq.pop();//특정 A > 현재 노드까지 최단 거리임을 확정, PQ에서 우선순위에 맞춰 뽑으니.

		//5. 추출된 노드에서 갈 수 있는 다른 후보 탐색
		for (int i = 0; i < alis[now.num].size(); ++i)
		{
			Edge next = alis[now.num][i];

			//다음 비용은 현재까지의 최소비용 + 다음 노드를 가기위한 비용
			int nextCost = next.cost + dist[now.num];
            
            //가지치기(정답비용보다 현재 경우가 더 큰 경우 continue)
			if (dist[next.num] <= nextCost)
				continue;
                
			pq.push({ next.num, nextCost });
			dist[next.num] = nextCost;
		}
	}

	//6. 정답 배열 출력
	cout << "Node : Cost\n";
	for (int i = 0; i < N; ++i)
		cout << i << " : " << dist[i] << "\n";
}

int main()
{
	cin >> N >> M;
	for (int i = 0; i < M; ++i)
	{
		int from, to, cost;
		cin >> from >> to >> cost;
		alis[from].push_back({ to, cost });
		alis[to].push_back({ from, cost });
	}

	dijkstra(0);

	return 0;
}

/*
input
정점: 9, 간선: 10, A 에서 B 로 가는 비용 C
9 10
0 2 2
2 3 37
2 4 5
1 4 17
3 5 11
4 5 45
4 6 9
5 7 4
6 7 9
7 8 28
*/

 

 

시간복잡도

- 간선의 개수: E

- 노드의 개수: V

- 모든 간선이 한 번씩 검사되기 때문에 O(E)

- 방문하는 간선을 priority queue에 넣는 시간 O(ElogE)

따라서, 복잡도는 O(E + ElogE)

 

최악의 경우(모든 노드가 서로 연결된 경우)에는 간선의 개수는 E = V(V-1) 로 이지만, 대부분의 그래프는 V^2 > E 를 만족한다.

O(ElogE) > O(ElogV^2) > O(2ElogV) > O(ElogV) : O(ElogV)