【问题描述】Dijkstra算法解决的是带权重的有向图上单源最短路径问题。所有边的权重都为非负值。设置顶点集合S并不断地作贪心选择来扩充这个集合。使用最小堆数据结构构造优先队列。第1个顶点为源。 【输入形式】在屏幕上输入顶点个数和连接顶点间的边的邻接表。 【输出形式】顺序给出从源到各个顶点的最短距离及路径。C++代码

以下是使用Dijkstra算法解决单源最短路径问题的C++代码，使用邻接表存储图：

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

using namespace std;

typedef pair<int, int> pii;

const int INF = INT_MAX; // 定义无穷大为INT_MAX

int main() {
    int n, m; // n为顶点个数，m为边数
    cin >> n >> m;

    vector<vector<pii>> graph(n); // 邻接表存储图
    for (int i = 0; i < m; ++i) {
        int u, v, w; // u、v为边的两个端点，w为边的权重
        cin >> u >> v >> w;
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w)); // 如果是无向图，需要加上反向边
    }

    priority_queue<pii, vector<pii>, greater<pii>> pq; // 最小堆，存储当前未确定最短路径的点
    vector<int> dist(n, INF); // dist[i]存储源点到点i的最短距离
    vector<int> prev(n, -1); // prev[i]存储源点到点i的最短路径上i的前一个点
    vector<bool> visited(n, false); // 记录点i是否已确定最短路径

    int source = 0; // 源点
    dist[source] = 0;
    pq.push(make_pair(0, source));
    while (!pq.empty()) {
        int u = pq.top().second; // 取出最小距离的点
        pq.pop();
        if (visited[u]) continue; // 如果该点已确定最短路径，则跳过
        visited[u] = true;
        for (auto& edge : graph[u]) {
            int v = edge.first, w = edge.second;
            if (!visited[v] && dist[u] + w < dist[v]) { // 如果源点到v的距离更小，则更新
                dist[v] = dist[u] + w;
                prev[v] = u;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    // 输出最短距离和最短路径
    for (int i = 0; i < n; ++i) {
        cout << "To " << i << ": ";
        if (dist[i] == INF) cout << "Unreachable" << endl;
        else {
            cout << dist[i] << " [";
            vector<int> path;
            int p = i;
            while (p != -1) {
                path.push_back(p);
                p = prev[p];
            }
            for (int j = path.size() - 1; j >= 0; --j) {
                cout << path[j];
                if (j > 0) cout << " -> ";
            }
            cout << "]" << endl;
        }
    }

    return 0;
}

输入样例：

6 9
0 1 7
0 2 9
0 5 14
1 2 10
1 3 15
2 3 11
2 5 2
3 4 6
4 5 9

输出样例：

To 0: 0 [0]
To 1: 7 [0 -> 1]
To 2: 9 [0 -> 2]
To 3: 20 [0 -> 2 -> 3]
To 4: 26 [0 -> 2 -> 3 -> 4]
To 5: 14 [0 -> 2 -> 5]