c++实现Dijkstra算法

以下是使用C++实现Dijkstra算法的示例代码：

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

using namespace std;

const int INF = 1e9; // 无穷大
const int MAXN = 1000; // 最大点数

vector<pair<int, int>> adj[MAXN]; // 邻接表存图
int dist[MAXN]; // 起点到各点的最短距离
bool visited[MAXN]; // 标记是否访问过

void dijkstra(int s) // s为起点
{
    fill(dist, dist + MAXN, INF); // 初始化dist数组为无穷大
    fill(visited, visited + MAXN, false); // 初始化visited数组为false

    dist[s] = 0; // 起点到自身的距离为0

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(dist[s], s)); // 将起点加入优先队列

    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();

        if (visited[u]) // 若u已被访问过，则跳过
            continue;

        visited[u] = true; // 标记u已被访问过

        for (auto v : adj[u])
        {
            int w = v.first;
            int weight = v.second;

            if (dist[u] + weight < dist[w]) // 更新距离
            {
                dist[w] = dist[u] + weight;
                pq.push(make_pair(dist[w], w)); // 将w加入优先队列
            }
        }
    }
}

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

    for (int i = 0; i < m; i++)
    {
        int u, v, weight;
        cin >> u >> v >> weight;

        adj[u].push_back(make_pair(v, weight));
        adj[v].push_back(make_pair(u, weight)); // 无向图，因此加入两条边
    }

    int s; // 起点
    cin >> s;

    dijkstra(s);

    for (int i = 0; i < n; i++)
        cout << "起点" << s << "到点" << i << "的最短距离为：" << dist[i] << endl;

    return 0;
}

代码中使用了邻接表存图，使用了STL中的优先队列来维护距离最小值，时间复杂度为$O(mlogn)$，其中n为点数，m为边数。