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

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

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

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

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

立即学习“C++免费学习笔记（深入）”；

Step 1：初始化。

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

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

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

动态WEB网站中的PHP和MySQL：直观的QuickPro指南第2版

动态WEB网站中的PHP和MySQL详细反映实际程序的需求，仔细地探讨外部数据的验证(例如信用卡卡号的格式)、用户登录以及如何使用模板建立网页的标准外观。动态WEB网站中的PHP和MySQL的内容不仅仅是这些。书中还提到如何串联JavaScript与PHP让用户操作时更快、更方便。还有正确处理用户输入错误的方法，让网站看起来更专业。另外还引入大量来自PEAR外挂函数库的强大功能，对常用的、强大的包

下载

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

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

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

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

Step 5：重复步骤3和步骤4。

重复步骤3和步骤4，直到所有的顶点都被访问过。最终，最短距离数组dist中存储的即为起始顶点到各个顶点的最短距离。

下面给出一个使用C++实现Dijkstra算法的代码示例：

#include 
#include 
#include 

using namespace std;

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

    vector dist(numVertices, INT_MAX); // 最短距离数组
    vector 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> 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 shortestDist = dijkstra(graph, 0);

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

    return 0;
}

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