Dijkstra's Algorithm

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

하나의 출발점에서 모든 정점까지의 최단 경로를 찾는 그래프 탐색 알고리즘.

음의 가중치를 가지지 않는 그래프에서 최단 경로를 찾는데 사용한다.

동작 방식

동작은 다음과 같다.

1. 출발점 설정 : 시작 정점 선택, 해당 정점의 최단 경로 값을 0으로 설정. 다른 정점들의 최단 경로 값을 무한대로 초기화.
2. 최단 경로 갱신 : 시작 정점과 인접한 정점들에 대해 거리 값 계산. 시작 정점으로부터 해당 정점까지의 거리와 현재까지 계산된 최단 경로 값을 비교해서 더 작은 값 선택. 만약, 선택한 정점의 최단 경로 값이 갱신된다면, 해당 정점을 경유하여 다른 정점까지의 최단 경로를 계산할 때 이를 고려한다.
3. 방문하지 않은 정점들 중에서 최단 경로 값이 가장 작은 정점을 선택한다. 이 정점을 현재 정점으로 설정하고, 방문한 것으로 표시한다.
4. 2-3단계를 모든 정점을 방문할때까지 반복한다.

매 단계에서 현재까지의 최단 경로를 선택하기에 최적의 결과를 보장한다.

pseudo code

function Dijkstra(Graph, source):
	distance[0:vertices] = inf 값
    visited[0:vertices] = false
    distance[source] = 0
    
    for i from 1 to |v|-1:
    	current = min(distance[not_visited])
        visited[current] = true
        
        for neighbor of current:
        	if(distance[current] + neighbor_weight < distance[neighbor])
            	distance[neighbor] = distance[current] + neighbor_weight
                
    return distance

C++ code

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#define INF INT_MAX

using namespace std;

struct Edge{
	int dest;
    int weight;
};

// 다익스트라 알고리즘 
void Dijkstra(vector<vector<Edge>>& graph, int source){
	int numVertices = graph.size();
    vector<int> distances(numVertices, INF);
    vector<bool> visited(numVertices, false);
    
    // 출발점의 거리를 0으로
    distances[source] = 0;
    
    // 우선순위 큐를 사용, 최단 거리 작은 정점 선택
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> pq;
    pq.push(make_pair(0, source));
    
    while(!pq.empty()){
    	int current = pq.top().second;
        pq.pop();
        
        // 이미 방문한 정점은 건너뜀
        if(visited[current])continue;
        
        visited[current] = true;
        
        // 현재 정점과 연결된 모든 인접 정점에 대해 최단 거리 갱신
       for(const Edge& edge : graph[current]){
       	int neighbor = edge.dest;
        int weight = edge.weight;
        
        if(distances[current]!=INF && distances[current] + weight < distances[neighbor]){
			distances[neighbor] = distances[current] + weight;
            pq.push(make_pair(distances[neighbor], neighbor));
        }
       }
    }
    
    // 결과 출력
    cout << "Vertex\tDistance from Source\n";
    for(int i=0;i<numVertices;++i){
		cout << i << "\t" << distances[i] << "\n";
    }
}

int main()
{
	int numVertices = 6;
    vector<vector<Edge>> graph(numVertices);
    
    // 그래프 초기화
    graph[0].push_back({1, 2});
    graph[0].push_back({2, 5});
    graph[1].push_back({2, 2});
    graph[1].push_back({3, 3});
    graph[1].push_back({4, 1});
    graph[2].push_back({3, 1});
    graph[2].push_back({4, 2});
    graph[3].push_back({4, 4});
    graph[3].push_back({5, 3});
    graph[4].push_back({5, 5});
    
    int source = 0;
    Dijkstra(graph, source);
    
    return 0;
}