最短路径dijkstra算法C++

Dijkstra算法是一种用于解决图中最短路径问题的贪心算法。它的基本思想是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法在解决非负权值图的单源最短路径问题上非常有效。下面是Dijkstra算法的C++代码实现：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f; // 表示正无穷

int n, m; // n表示点数，m表示边数
int dis[MAX]; // dis数组用于存储起点到各个点的最短距离
bool vis[MAX]; // vis数组用于判断该点是否已经被访问

struct Edge
{
    int to; // 终点
    int cost; // 边权
};

vector<Edge> G[MAX]; // G为邻接表，用于存储图中的边

void dijkstra(int s)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    memset(dis, INF, sizeof(dis)); // 将dis数组初始化为正无穷
    memset(vis, false, sizeof(vis)); // 将vis数组初始化为false
    dis[s] = 0; // 起点到自己的距离为0
    q.push(make_pair(dis[s], s)); // 将起点入队

    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i].to;
            int cost = G[u][i].cost;
            if (dis[v] > dis[u] + cost)
            {
                dis[v] = dis[u] + cost;
                q.push(make_pair(dis[v], v));
            }
        }
    }
}

int main()
{
    cin >> n >> m; // 输入点数和边数
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back((Edge){v, w});
        G[v].push_back((Edge){u, w}); // 无向图需要反向建边
    }

    dijkstra(1); // 以1号点为起点求最短路径

    for (int i = 1; i <= n; i++)
    {
        cout << dis[i] << " ";
    }
    cout << endl;

    return 0;
}