dijkstra c++

Dijkstra算法是一种单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。以下是C++实现dijkstra算法的代码和注释：

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h> //用于定义INT_MAX

using namespace std;

// 定义图中的边
struct Edge{
    int to; // 目标节点
    int weight; // 边的权重
    Edge(int t, int w):to(t), weight(w){} // 构造函数
};

// 定义邻接表
typedef vector<vector<Edge>> Graph;

// Dijkstra算法
vector<int> dijkstra(const Graph &graph, int start){
    vector<int> dist(graph.size(), INT_MAX); // 初始化距离为INT_MAX
    dist[start] = 0; // 起点的距离为0

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
    que.push(make_pair(dist[start], start)); // 将起点入队

    while(!que.empty()){
        pair<int, int> p = que.top(); que.pop();
        int v = p.second;
        if(dist[v] < p.first) continue; // 如果当前距离比已知距离小，则跳过
        for(int i=0; i<graph[v].size(); i++){
            Edge e = graph[v][i];
            if(dist[e.to] > dist[v] + e.weight){
                dist[e.to] = dist[v] + e.weight; // 更新最短距离
                que.push(make_pair(dist[e.to], e.to)); // 将更新后的节点入队
            }
        }
    }
    return dist;
}

int main(){
    int V, E, r;
    cin >> V >> E >> r;

    Graph graph(V);
    for(int i=0; i<E; i++){
        int s, t, d;
        cin >> s >> t >> d;
        graph[s].push_back(Edge(t, d)); // 添加边
    }

    vector<int> dist = dijkstra(graph, r);

    for(int i=0; i<V; i++){
        if(dist[i] == INT_MAX){
            cout << "INF" << endl;
        }else{
            cout << dist[i] << endl;
        }
    }

    return 0;
}

该代码实现了对于给定的加权有向图，计算从起点到其他所有点的最短路径，并输出最短路径的距离。其中包含了对图的邻接表定义、定义图中边、Dijkstra算法的实现和主函数。