如何使用C++中的Dijkstra算法

如何使用C++中的Dijkstra算法？

Dijkstra算法是一种用于求解带权重有向图中两个顶点之间最短路径的贪心算法。它的核心思想是通过不断更新起始顶点到其他顶点的最短距离来逐步扩展最短路径。

下面将介绍如何使用C++实现Dijkstra算法，并给出具体的代码示例。

实现Dijkstra算法需要以下几个步骤：

Step 1：初始化。

首先，我们需要初始化一些数据结构，包括起始顶点start、最短距离数组dist和访问状态数组visited。起始顶点start指定了最短路径的起点，最短距离数组dist用于记录起始顶点到其他顶点的当前最短距离，访问状态数组visited用于标记顶点是否已经被访问过。

Step 2：初始化最短距离数组。

将起始顶点到其他顶点的最短距离初始化为无穷大，起始顶点到自身的最短距离初始化为0。同时将起始顶点标记为已访问。

Step 3：更新最短距离数组。

对于起始顶点相邻的所有顶点，如果通过起始顶点能够找到更短的路径，则更新最短距离数组。具体的更新方式是将起始顶点到当前顶点的距离加上起始顶点到当前顶点的边的权重，与当前顶点原始的最短距离进行比较。

Step 4：选取下一个最近顶点。

从尚未访问的顶点中选取距离起始顶点最近的顶点作为下一个要访问的顶点。

Step 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;
}

在上述代码中，我们通过一个二维矩阵表示带权重的有向图，矩阵中的每个元素表示两个顶点之间的边的权重。最终输出起始顶点到各个顶点的最短距离。

以上是如何使用C++中的Dijkstra算法的详细内容。更多信息请关注PHP中文网其他相关文章！