C++에서 Dijkstra 알고리즘을 사용하는 방법

C++에서 Dijkstra의 알고리즘을 사용하는 방법은 무엇입니까?

Dijkstra의 알고리즘은 가중치가 적용된 유향 그래프에서 두 정점 사이의 최단 경로를 찾는 데 사용되는 그리디 알고리즘입니다. 핵심 아이디어는 시작 정점에서 다른 정점까지의 최단 거리를 지속적으로 업데이트하여 최단 경로를 점진적으로 확장하는 것입니다.

다음에서는 C++를 사용하여 Dijkstra 알고리즘을 구현하는 방법을 소개하고 구체적인 코드 예제를 제공합니다.

Dijkstra의 알고리즘을 구현하려면 다음 단계가 필요합니다.

1단계: 초기화.

먼저 시작 정점 시작, 최단 거리 배열 dist 및 방문한 방문 상태 배열을 포함한 일부 데이터 구조를 초기화해야 합니다. 시작 정점 start는 최단 경로의 시작점을 지정하고, 최단 거리 배열 dist는 시작 정점에서 다른 정점까지의 현재 최단 거리를 기록하는 데 사용되며, 방문한 액세스 상태 배열은 정점을 방문했는지 여부를 표시하는 데 사용됩니다. .

2단계: 최단 거리 배열을 초기화합니다.

시작 정점에서 다른 정점까지의 최단 거리를 무한대로 초기화하고, 시작 정점에서 자신까지의 최단 거리를 0으로 초기화합니다. 또한 시작 정점을 방문한 것으로 표시합니다.

3단계: 최단 거리 배열을 업데이트합니다.

시작 정점에 인접한 모든 정점에 대해 시작 정점을 통해 더 짧은 경로를 찾을 수 있는 경우 최단 거리 배열을 업데이트합니다. 구체적인 업데이트 방법은 시작 정점에서 현재 정점까지의 거리에 시작 정점부터 현재 정점까지의 가장자리 가중치를 더한 값을 현재 정점에서 원래의 최단 거리와 비교하는 것입니다.

4단계: 다음으로 가장 가까운 정점을 선택합니다.

방문하지 않은 정점 중 시작 정점에 가장 가까운 정점을 방문할 다음 정점으로 선택합니다.

5단계: 3단계와 4단계를 반복합니다.

모든 정점을 방문할 때까지 3단계와 4단계를 반복합니다. 마지막으로 최단 거리 배열 dist에 저장되는 것은 시작 정점에서 각 정점까지의 최단 거리입니다.

다음은 C++를 사용하여 Dijkstra의 알고리즘을 구현하는 코드 예제입니다.

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

vector<int> dijkstra(vector<vector<int>>& graph, int start) {
    int numVertices = graph.size();

    vector<int> dist(numVertices, INT_MAX); // 最短距离数组
    vector<bool> visited(numVertices, false); // 访问状态数组

    dist[start] = 0;

    for (int i = 0; i < numVertices - 1; i++) {
        int minDist = INT_MAX;
        int minIndex = -1;
        
        // 选取下一个最近顶点
        for (int j = 0; j < numVertices; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                minIndex = j;
            }
        }

        visited[minIndex] = true;

        // 更新最短距离数组
        for (int j = 0; j < numVertices; j++) {
            if (!visited[j] && graph[minIndex][j] && dist[minIndex] != INT_MAX && dist[minIndex] + graph[minIndex][j] < dist[j]) {
                dist[j] = dist[minIndex] + graph[minIndex][j];
            }
        }
    }

    return dist;
}

int main() {
    vector<vector<int>> graph = {
        {0, 2, 4, 0, 0},
        {2, 0, 1, 3, 0},
        {4, 1, 0, 0, 2},
        {0, 3, 0, 0, 3},
        {0, 0, 2, 3, 0}
    };

    vector<int> shortestDist = dijkstra(graph, 0);

    cout << "起始顶点到各个顶点的最短距离：" << endl;
    for (int i = 0; i < shortestDist.size(); i++) {
        cout << "到顶点 " << i << " 的最短距离为：" << shortestDist[i] << endl;
    }

    return 0;
}

위 코드에서는 2차원 행렬을 통해 가중치가 적용된 방향성 그래프를 표현합니다. 행렬의 각 요소는 두 정점 사이의 거리를 나타냅니다. 무게. 마지막으로 시작 정점에서 각 정점까지의 최단 거리가 출력됩니다.

위 내용은 C++에서 Dijkstra 알고리즘을 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!