Dijkstra 算法C++

Dijkstra算法是一种用于图搜索的算法，用于找到从一个节点到所有其他节点的最短路径。这个算法的原理是通过不断更新节点的距离值，从而找到最短路径。可以使用邻接矩阵来存储图的信息，其中g[a][b]表示点a到点b的距离。

下面是一个用C++编写的Dijkstra算法的示例代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510;
int g[N][N];
int dis[N];
int n, m;
bool st[N];

int dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    dis = 0;
    for (int i = 0; i < n-1; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!st[j && (t == -1 || dis[t > dis[j])) {
                t = j;
            }
        }
        for (int j = 1; j <= n; j++) {
            dis[j = min(dis[j], dis[t + g[t][j]);
        }
        st[t = true;
    }
    if (dis[n == 0x3f3f3f3f) {
        return -1;
    }
    return dis[n];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y = min(g[x][y], z);
    }

    cout << dijkstra() << endl;
    
    return 0;
}

以上是一个基于邻接矩阵的Dijkstra算法的完整C++代码示例。首先，我们输入图中的节点数n和边数m，然后根据输入的边的信息，初始化邻接矩阵g。接下来，我们调用dijkstra函数来计算最短路径，并将结果输出。