用C++写【问题描述】Dijkstra算法解决的是带权重的有向图上单源最短路径问题。所有边的权重都为非负值。设置顶点集合S并不断地作贪心选择来扩充这个集合。使用最小堆数据结构构造优先队列。最后一个结点为源

点，对于源点到其他点的所有路径，Dijkstra算法会计算出最短路径。在实现Dijkstra算法时，需要用一个数组来记录源点到每个顶点的最短距离，以及一个数组来记录每个顶点的前驱结点，以便最后输出最短路径。

以下是用C++写的Dijkstra算法示例代码：

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

using namespace std;

const int MAX = 100; // 最大顶点数

vector<pair<int, int>> graph[MAX]; // 邻接表表示的图
int dist[MAX]; // 记录源点到每个顶点的最短距离
int prev[MAX]; // 记录每个顶点的前驱结点
bool visited[MAX]; // 记录每个顶点是否已经被访问

void dijkstra(int start, int n) {
    // 初始化
    for (int i = 0; i < n; i++) {
        dist[i] = INT_MAX;
        prev[i] = -1;
        visited[i] = false;
    }
    dist[start] = 0;

    // 用最小堆实现优先队列
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, start));

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (visited[u]) {
            continue;
        }
        visited[u] = true;
        for (auto v : graph[u]) {
            if (dist[u] + v.second < dist[v.first]) {
                dist[v.first] = dist[u] + v.second;
                prev[v.first] = u;
                pq.push(make_pair(dist[v.first], v.first));
            }
        }
    }
}

int main() {
    int n = 6; // 顶点数
    int m = 8; // 边数

    // 构造图
    graph[0].push_back(make_pair(1, 6));
    graph[0].push_back(make_pair(2, 2));
    graph[1].push_back(make_pair(2, 3));
    graph[1].push_back(make_pair(3, 1));
    graph[2].push_back(make_pair(1, 2));
    graph[2].push_back(make_pair(3, 5));
    graph[2].push_back(make_pair(4, 3));
    graph[3].push_back(make_pair(4, 1));
    graph[3].push_back(make_pair(5, 5));
    graph[4].push_back(make_pair(5, 2));

    dijkstra(0, n); // 求从0号顶点出发的最短路径

    // 输出结果
    for (int i = 0; i < n; i++) {
        cout << "Vertex " << i << ": distance = " << dist[i] << ", path = ";
        int j = i;
        while (j != -1) {
            cout << j << " ";
            j = prev[j];
        }
        cout << endl;
    }

    return 0;
}

在上面的代码中，我们使用了一个邻接表来表示图，其中每个元素是一个pair，表示一条边，第一个元素是目标顶点的编号，第二个元素表示边的权重。dist数组记录源点到每个顶点的最短距离，prev数组记录每个顶点的前驱结点，visited数组记录每个顶点是否已经被访问。在dijkstra函数中，我们首先初始化dist、prev和visited数组，然后用最小堆实现优先队列，将源点加入队列。每次从队列中取出距离源点最近的顶点u，将其标记为已访问，然后依次遍历u的邻居v，如果从源点到v的距离比已知的更短，则更新dist和prev数组，并将v加入队列。最后输出每个顶点的最短路径。