[알고리즘] Dijkstra's Algorithm (최단거리 구하기 - 다익스트라)

Dijkstra's Algorithm 

네덜란드의 컴퓨터 과학자 Edsger W. Dijkstra의 이름을 딴 Dijkstra의 알고리즘은 그래프 순회 알고리즘으로 음이 아닌 간선 가중치를 갖는 그래프에서 노드들 사이의 최단 경로를 찾는 데 사용됩니다.
 

출처 : 위키피디아 - Dijkstra's Algorithm

 
이 알고리즘은 방문한 노드들의 집합과 소스 노드로부터 다른 모든 노드들에 대한 잠정적인 거리를 계속 업데이트 하면서 최단 거리를 찾는 과정이 필요합니다.

1. 처음에는 소스 노드까지의 거리를 0으로 설정하고, 다른 모든 노드까지의 거리를 무한대로 설정한다.
2. 각 단계에서 알고리즘은 아직 방문하지 않은 소스 노드로부터 잠정 거리가 가장 작은 노드를 선택한다.
3. 그 다음 선택된 노드의 모든 이웃 노드를 검사하고 더 짧은 경로가 발견되면 그들의 잠정 거리를 업데이트한다.
4. 이 프로세스는 모든 노드가 방문되거나 대상 노드로 가는 최단 경로가 발견될 때까지 계속된다.
5. 마지막으로, 알고리즘은 소스 노드로부터 각 노드로의 최단 경로 및 각각의 거리를 반환한다.

 

다익스트라의 알고리즘은 네트워크 라우팅 프로토콜, GPS 네비게이션 시스템, 교통망에서 최단 경로를 찾는 등 다양한 응용 분야에서 흔히 사용됩니다.

※ 그래프에 음의 간선 가중치가 포함된 경우 다익스트라의 알고리즘이 올바른 결과를 도출하지 못할 수 있다는 점에 유의해야 한다. 이러한 경우, 벨만-포드 또는 A* 알고리즘과 같은 다른 알고리즘이 더 적합할 수 있습니다.
 
 

Implementation

아래는 C Code 기반의 다익스트라 코드 입니다.
개념이해를 위해서는 C 언어 기반으로 작성된 코드를 추가하였습니다.  효율 데이터 처리를 위해서 Priority Queue 를 사용하는 방법도 있는데 이 부분은 추후 다시 소개하겠습니다.
 
int graph[MAX_VERTICES][MAX_VERTICES];
-> 인접 행렬로 표시되는 그래프

bool visited[MAX_VERTICES];
-> 방문 여부를 표시하기 위한 visited 저장 공간
int distances[MAX_VERTICES];

-> Start Node 로 부터 특정 Node 까지의 거리를 Update 하기 위한 저장공간

#define MAX_VERTICES 100

int graph[MAX_VERTICES][MAX_VERTICES];
bool visited[MAX_VERTICES];
int distances[MAX_VERTICES];

 
initializedGraph() 는 방문 데이터 및 거리, graph 를 초기화 하는 함수
addEdge() 는 2개의 Node 간 가중치(weight) 와 함께 Edge 를 연결한다.

void initializeGraph() {
    for (int i = 0; i < MAX_VERTICES; i++) {
        visited[i] = false;
        distances[i] = INT_MAX;
        for (int j = 0; j < MAX_VERTICES; j++) {
            graph[i][j] = 0;
        }
    }
}

void addEdge(int u, int v, int weight) {
    graph[u][v] = weight;
    graph[v][u] = weight;
}

 
int getMinDistanceVertex(int numVertices) :  Node 의 간선 중에서 가장 짧은 거리를 찾아주는 함수
아직 방문하지 않은 Node 중( !visited[i] ) 에서 가장 작은 distance를 가지고 있는 Node 를 찾아줍니다.

int getMinDistanceVertex(int numVertices) {
    int minDistance = INT_MAX;
    int minIndex = -1;

    for (int i = 0; i < numVertices; i++) {
        if (!visited[i] && distances[i] < minDistance) {
            minDistance = distances[i];
            minIndex = i;
        }
    }

    return minIndex;
}

 

현재 Node : u <-- getMinDistanceVertex() 를 통해 찾은 방문하지 않은 Node 중 최단 거리의 Node
distaces[v] 가 distaces[u] + distaces[u][v] 보다 크다면 distaces[v] 에 새로운 최단 거리를 업데이트 해준다.
※ 현재 코드에서는 경로를 알수는 없고, 목적지까지의 최단 거리만 기록하게 된다.

void dijkstra(int startVertex, int numVertices) {
    distances[startVertex] = 0;
    
    // Find shortest path for all vertices
    //! 이 예제 코드는 무조건 for 문을 돌려서 모든 Node 의 distance 를 계산할 것이다.
    for (int count = 0; count < numVertices - 1; count++) {
   		// Pick the minimum distance vertex from the set of vertices not yet processed.
        int u = getMinDistanceVertex(numVertices);
        
        // Mark the picked vertex as processed
        visited[u] = true;

       // Update dist value of the adjacent vertices of the picked vertex.
       //! 이 예제 코드는 무조건 for 문을 돌려서 모든 Node 의 distance 를 계산할 것이다.
        for (int v = 0; v < numVertices; v++) {
        
        	// 현재 Node : u <-- getMinDistanceVertex() 에서 받아왔다.
            // 이동할 위치 : v (0 ~ numVertices)
            // distaces[v] 가 distance[u] + graph[u][v] 보다 크다면
            // distaces[v] 에 새로운 최단 거리를 업데이트 해준다.
            //! 현재 코드에서는 경로를 알수는 없고, 목적지까지의 최단 거리만 기록하게 된다.
            if (!visited[v] && graph[u][v] && distances[u] != INT_MAX &&
                distances[u] + graph[u][v] < distances[v]) {
                distances[v] = distances[u] + graph[u][v];
            }
        }
    }
}

 
지금까지의 코드를 실행하기 위한 main 함수 입니다.

int main() {
    int numVertices, numEdges;
    std::cout << "Enter the number of vertices: ";
    std::cin >> numVertices;
    std::cout << "Enter the number of edges: ";
    std::cin >> numEdges;

    initializeGraph();

    int u, v, weight;
    for (int i = 0; i < numEdges; i++) {
        std::cout << "Enter edge " << i + 1 << " (u v weight): ";
        std::cin >> u >> v >> weight;
        addEdge(u, v, weight);
    }

    int startVertex;
    std::cout << "Enter the starting vertex for Dijkstra's algorithm: ";
    std::cin >> startVertex;

    dijkstra(startVertex, numVertices);

    std::cout << "Shortest distances from vertex " << startVertex << ":\n";
    for (int i = 0; i < numVertices; i++) {
        std::cout << "Vertex " << i << ": " << distances[i] << "\n";
    }

    return 0;
}

 
읽어주셔서 감사합니다.
다음에는 Priority Queue 를 사용한 다른 다익스트라 코드를 정리하여 공유하도록 하겠습니다.
 
※ 더 좋은 알고리즘 설명을 위해 코드 예제와 같은 내용은 계속 업데이트 될 것입니다.