C++ 编程实现Dijkstra最短路径算法并输出

以下是C++实现Dijkstra最短路径算法的示例代码，其中使用邻接矩阵存储图：

#include <iostream>
#include <climits>
using namespace std;

const int MAXN = 100;  // 最大节点数
int g[MAXN][MAXN];     // 邻接矩阵表示图
int d[MAXN];           // 存储源点到各个节点的最短距离
bool vis[MAXN];        // 标记节点是否已经被访问过

// 计算从源点s到各个节点的最短路径
void dijkstra(int s, int n)
{
    // 初始化
    for (int i = 0; i < n; i++) {
        d[i] = (i == s) ? 0 : INT_MAX;
        vis[i] = false;
    }

    // 循环n次，每次找到一个节点的最短路径
    for (int i = 0; i < n; i++) {
        // 找到当前未访问过的节点中距离源点最近的节点
        int u = -1, min_d = INT_MAX;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && d[j] < min_d) {
                u = j;
                min_d = d[j];
            }
        }
        if (u == -1) break;  // 如果没有找到可达的节点，退出循环

        vis[u] = true;  // 标记u为已访问过

        // 更新从u出发能到达的所有节点的最短路径
        for (int v = 0; v < n; v++) {
            if (!vis[v] && g[u][v] != INT_MAX) {
                d[v] = min(d[v], d[u] + g[u][v]);
            }
        }
    }
}

int main()
{
    int n, m, s, t;
    cin >> n >> m >> s >> t;

    // 初始化邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g[i][j] = INT_MAX;
        }
    }

    // 读入图的边
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = w;
    }

    dijkstra(s, n);  // 计算从s到各个节点的最短路径

    // 输出结果
    if (d[t] == INT_MAX) {
        cout << "No path from " << s << " to " << t << endl;
    } else {
        cout << "Shortest path from " << s << " to " << t << " is " << d[t] << endl;
    }

    return 0;
}

其中，n表示图的节点数，m表示边数，s表示源点，t表示目标点。读入图的边后，调用dijkstra函数计算从s到各个节点的最短路径。最后输出从s到t的最短路径长度。如果没有从s到t的路径，则输出"No path from s to t"。