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

다익스트라

• 가중 그래프에서 최단경로를 찾는 알고리즘
• 모든 링크의 가중치는 양의 정수여야 한다.
• 단일 시작점에서 시작하여 그래프의 모든 정점으로의 최단 경로를 계산하는 One To All 방식
• 시간복잡도 O((V+E) log V)

 

 

동작 방식

 

 

다익스트라 알고리즘 - https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

1. 출발 노드 설정, 최단 거리 테이블 초기화
   1. 모든 버텍스 간의 최단거리 값 무한대 설정. 시작 버텍스는 0
2. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드 선택
3. 해당 노드를 거쳐 다른 노드로 가는 비용(최단거리 값 + 가중치)업데이트
   1. 기존 최단 거리 값보다 작을 시 테이블 업데이트
4. 2~3의 과정 반복
5. 각 정점에 대한 최단 거리 값 반환

 

다익스트라 (+ 우선순위 큐) 구현 코드

#define INF 1e9


// 거리(가중치) / 노드 번호
vector<vector<pair<int, int>>> graph; 

// 최단거리 테이블
vector<int> distances;



void Dijkstra(int start, int numVertices)
{


	// 우선순위 큐 (거리 , 노드 인덱스)
	priority_queue<pair<int, int>> pq;

	// 시작 정점의 거리 0 설정
	distances[start] = 0;	
	pq.push({ 0, start });

	while (!pq.empty())
	{
		// 현재 정점까지의 거리
		int currentDistance = pq.top().first;
		// 현재 정점
		int currentVertex = pq.top().second;
		pq.pop();

		// 이미 처리된 정점일 경우
		if (currentDistance > distances[currentVertex])
			continue;

		// 현재 정점의 모든 인접 정점 확인
		for (pair<int, int>& edge : graph[currentVertex])
		{
			int weight = edge.first;
			int neighbor = edge.second;

			// 비용이 더 적은 경로 발견된 경우
			if (distances[currentVertex] + weight < distances[neighbor])
			{
				distances[neighbor] = distances[currentVertex] + weight;
				pq.push({ distances[neighbor], neighbor });
			}
		}
	}
}

	graph.resize(6 + 1);
	distances.assign(6 + 1, INF);



	graph[0].emplace_back(7, 1);
	graph[0].emplace_back(9, 2);
	graph[0].emplace_back(14, 5);
	graph[1].emplace_back(10, 2);
	graph[1].emplace_back(15, 3);
	graph[2].emplace_back(2, 5);
	graph[2].emplace_back(11, 3);
	graph[3].emplace_back(6, 4);
	graph[5].emplace_back(9, 4);


	Dijkstra(0, 6);

	for (int i = 0; i <= 5; i++)
	{
		if (distances[i] == INF)
		{
			cout << i+1 << ": Unreachable" << endl;
		}
		else
		{
			cout << i+1 << ": " << distances[i] << endl;
		}
	}