邻接矩阵求最短路径c++

邻接矩阵求最短路径可以使用 Dijkstra 算法来实现，具体的 C++ 代码如下：

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

const int MAXN = 100;
const int INF = INT_MAX;

int n; // 节点数
int m; // 边数
int s; // 起点
int t; // 终点

int g[MAXN][MAXN]; // 邻接矩阵表示图
int dis[MAXN]; // 起点到各个点的最短距离
bool vis[MAXN]; // 记录每个点是否已经确定最短距离

void dijkstra() {
    // 初始化
    for (int i = 1; i <= n; i++) {
        dis[i] = g[s][i];
        vis[i] = false;
    }
    dis[s] = 0;
    vis[s] = true;

    // 每次确定一个点的最短距离
    for (int i = 1; i <= n; i++) {
        int minDis = INF;
        int minIndex = -1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && dis[j] < minDis) {
                minDis = dis[j];
                minIndex = j;
            }
        }
        if (minIndex == -1) break;
        vis[minIndex] = true;

        // 更新其他点的距离
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && g[minIndex][j] != INF) {
                dis[j] = min(dis[j], dis[minIndex] + g[minIndex][j]);
            }
        }
    }
}

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

    // 初始化邻接矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            g[i][j] = INF;
        }
    }
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = w;
    }

    dijkstra();

    cout << dis[t] << endl;

    return 0;
}

其中，邻接矩阵 `g` 的初始化值为 `INF`，表示两个节点之间没有边相连。在输入边时，需要将两个节点之间的距离存储在邻接矩阵中。`dijkstra` 函数中，首先初始化起点到各个点的距离，然后每次选择一个未确定最短距离的点，更新其他点的距离，直到所有点的最短距离都被确定。最终，起点到终点的最短距离存储在 `dis[t]` 中。