C++简单实现Dijkstra算法

前言

Dijkstra算法是一种用于找到最短路径的图算法，它由荷兰计算机科学家Edsger Dijkstra在1956年提出。该算法的输入是一个加权有向图和一个起始顶点，通过计算从起始顶点到图中所有其他顶点的最短路径长度，并记录路径，最终输出起始顶点到其他顶点的最短路径。Dijkstra算法具有广泛的应用，例如路由器选择最佳路径、GPS导航等。

算法实现详解

首先，我们需要定义图的表示方式。在C++中，常用的图的表示方式有邻接矩阵和邻接表。这里我们选择使用邻接矩阵来表示加权有向图。使用邻接矩阵可以方便地获取两个顶点之间的边的权重，并且可以使用二维数组来表示图的连接关系。

// 定义图的邻接矩阵
vector> graph(n, vector(n, -1));

// 初始化邻接矩阵
for (int i = 0; i < edges.size(); ++i) {
    int u = edges[i][0];
    int v = edges[i][1];
    int w = edges[i][2];
    graph[u][v] = w;
}

接下来，我们需要实现Dijkstra算法的核心部分。在算法的初始化阶段，我们将所有顶点的最短路径初始化为无穷大，然后将起始顶点的最短路径设为0。然后，我们从起始顶点开始，逐个更新其他顶点的最短路径。在每次更新时，我们选择当前最短路径集合中距离最小的顶点，并通过该顶点更新其他未访问的顶点的最短路径。我们使用一个优先队列来存储未访问的顶点，并按照最短路径的距离进行排序。

// 定义最短路径和访问状态数组
vector dist(n, INT_MAX); // 存储最短路径
vector visited(n, false); // 记录是否访问

// 初始化起始顶点的最短路径
dist[start] = 0;

// 定义优先队列，按照最短路径进行排序
priority_queue, vector>, greater>> pq;
pq.push({0, start});

while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();

    // 如果顶点已经访问过，跳过
    if (visited[u]) {
        continue;
    }

    visited[u] = true;

    // 更新其他未访问顶点的最短路径
    for (int v = 0; v < n; ++v) {
        if (graph[u][v] != -1 && !visited[v]) {
            int newDist = dist[u] + graph[u][v];
            if (newDist < dist[v]) {
                dist[v] = newDist;
                pq.push({dist[v], v});
            }
        }
    }
}

代码解释与规范

首先，我们使用了C++中的向量(vector)来表示邻接矩阵。向量是一个动态数组，它可以根据需要自动调整大小，非常方便。我们使用二维向量来表示邻接矩阵，其中第一维表示起点，第二维表示终点，而每个元素则是边的权重。初始化时，我们将所有边的权重设置为-1，表示无连接。

然后，在Dijkstra算法的实现中，我们使用了两个主要的数据结构，即最短路径数组(dist)和访问状态数组(visited)。最短路径数组用于存储从起始点到每个顶点的最短路径长度，初始时均设置为无穷大。访问状态数组用于标记每个顶点是否已被访问过，初始时均设置为false。

在Dijkstra算法的主循环中，我们通过优先队列来选择当前最短路径集合中距离最小的顶点。优先队列是一种能够自动排序的队列，该队列中的元素会根据指定的排序准则进行排序。在本算法中，我们使用了一个小顶堆实现的优先队列，并根据最短路径的距离进行排序，保证每次取出的顶点都是最短路径集合中距离最小的顶点。

总结

通过以上的代码和解释，我们实现了C++版本的Dijkstra算法。该算法能够在加权有向图中找到起始顶点到其他顶点的最短路径，并计算出最短路径的长度。在算法实现中，我们使用了邻接矩阵来表示图，采用了优先队列来选择最短路径，同时还使用了向量来存储相关信息。这个实现能够有效地解决需要找到最短路径的问题，例如路由器选择最优路径和GPS导航等。