[Algorithm] Dijkstra

Dijkstra algorithm

• 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘
• 간선들 중 단 하나라도 가중치가 음수이면 사용 X
• 시간복잡도 O((V+E)logV))
  • 각 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는 데 O(VlogV)
  • 각 노드마다 이웃한 노드의 최단 거리 갱신 O(ElogV)

Process of operation

• initialization
  • 거리를 저장하는 배열에 모두 INF 값으로 초기화
• greedy access
  • priority queue(min heap)를 사용해 시작 노드에서부터 가장 적은 비용을 가지는 길목을 선택하여 다음 노드들을 방문
• update distance
  • 위의 접근에서 특정 노드에 도착했을 때, 거리 배열의 값보다 현재 거쳐온 경로의 비용이 작다면 새로 갱신

void dijkstra(int src) {
	priority_queue<pii, vector<pii>, greater<pii>> pq;  // first : cost / second : node
	for (int i = 1; i <= v; ++i) dist[i] = INF; // initialize distance to INF
	dist[src] = 0;
	pq.push({ 0, src });  // start with source

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

	// filtering the case which cost is higher than dist[cur]
		if(dist[cur] < cost) continue;

    // visit all nodes which connected to a current node
		for (int i = 0; i < (int)graph[cur].size(); ++i) {
			int next = graph[cur][i].first;
			int nCost = graph[cur][i].second;

      // greedy access with selecting a shortest path
			if (dist[next] <= dist[cur] + nCost) continue;
			dist[next] = dist[cur] + nCost;
      // by pushing {cost, next node}, priority queue continuously updates shortest paths to the top
			pq.push({ dist[next], next });
		}
	}
}

백준 예제 문제집

---

ref :
C++ 다익스트라(Dijkstra)
나동빈님 블로그