Dijkstra算法是一种用于在加权图中找到单源最短路径的经典算法。

基本原理：

1. 数据结构：

   • 使用一个优先队列（通常使用最小堆实现）来存储待访问的节点，按照节点到起始节点的距离排序。
   • 使用一个距离数组dist[]来记录每个节点到起始节点的当前最短距离。

2. 算法步骤：

   • 初始化：将起始节点的距离设为0，其他节点的距离设为无穷大。
   • 从优先队列中选取当前距离起始节点最近的节点，标记为已访问。
   • 更新与该节点相邻节点的距离值，如果经过当前节点到相邻节点的路径距离小于相邻节点当前记录的距离值，则更新距离值。
   • 将更新后的节点加入优先队列中，重复步骤，直到所有节点都被访问。

     ---

详细步骤：

1. 初始化：

   • 将起始节点的距离设为0，其他节点的距离设为无穷大。
   • 将起始节点加入优先队列。

2. 循环：

   • 从优先队列中取出距离起始节点最近的节点u。
   • 遍历节点u的所有邻居节点v：
     • 如果 dist[u] + weight(u, v) < dist[v]，更新节点v的距离值为dist[u] + weight(u, v)。
     • 更新完后，将节点v加入优先队列。

3. 重复：

   • 重复以上步骤，直到优先队列为空或者目标节点被标记为已访问。

特点和优化：

• Dijkstra算法适用于无负权边的图。
• 算法的时间复杂度为O((V + E) log V)，其中V为节点数，E为边数。
• 使用优先队列可以提高算法效率，但在稠密图中可能效率较低。
• 可以通过使用堆优化算法（如Fibonacci堆）来进一步优化Dijkstra算法的性能。

示例应用：

• 网络路由：在计算机网络中寻找最短路径。
• 交通规划：在地图应用中找到最短驾驶路径。
• 资源分配：在项目管理中确定资源分配路径。

代码示例：

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

using namespace std;

#define INF INT_MAX // 无穷大

// 边的结构体
struct Edge {
    int to;
    int weight;
};

// 图的结构体
struct Graph {
    vector<vector<Edge>> adjList;
    int V; // 节点数

    Graph(int V) : V(V) {
        adjList.resize(V);
    }

    // 添加边
    void addEdge(int from, int to, int weight) {
        adjList[from].push_back({to, weight});
    }

    // Dijkstra算法
    void dijkstra(int src) {
        vector<int> dist(V, INF);
        dist[src] = 0;

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, src});

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

            for (const Edge& edge : adjList[u]) {
                int v = edge.to;
                int weight = edge.weight;

                if (dist[u] != INF && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.push({dist[v], v});
                }
            }
        }

        // 输出最短路径
        cout << "最短路径距离从节点" << src << "到各个节点：" << endl;
        for (int i = 0; i < V; ++i) {
            cout << "节点 " << i << ": " << dist[i] << endl;
        }
    }
};

补充说明：

在C++中，priority_queue是一个优先队列容器，它按照特定的顺序来处理元素。

• priority_queue是C++标准库中的一个容器适配器，它提供了队列的功能，但是按照元素的优先级来访问元素，而不是按照它们被加入队列的顺序。

• <pair<int, int>>指定了priority_queue中的元素类型为pair<int, int>，即每个元素是一个整型的pair，第一个整数表示节点到源节点的距离，第二个整数表示节点的索引。

• vector<pair<int, int>>是底层容器，用于存储priority_queue的元素。在这里，我们使用vector来存储pair<int, int>。

• greater<pair<int, int>>是一个函数对象，它定义了优先队列中元素的比较规则。在本例中，greater表示按照从小到大的顺序排列元素，这意味着队列的顶部元素是最小的。顶部最大的规则定义为less.

---

P1. 洛谷p1807最长路

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

using namespace std;

#define INF -200000 

struct Edge {
    int to;
    int weight;
};

struct Graph {
    vector<vector<Edge>> adjList;
    int V; // 节点数

    Graph(int V) : V(V) {
        adjList.resize(V);
    }

    // 添加边
    void addEdge(int from, int to, int weight) {
        adjList[from].push_back({to, weight});
    }

    void dijkstra(int src) {
        vector<int> dist(V, INF);
        dist[src] = 0;

        priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pq;
        pq.push({0, src});

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

            for (const Edge& edge : adjList[u]) {
                int v = edge.to;
                int weight = edge.weight;

                if (dist[u] != INF && dist[u] + weight > dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.push({dist[v], v});
                }
            }
        }
        cout<<dist[V-1];
        //for (int i = 0; i < V; ++i) {cout << "节点 " << i << ": " << dist[i] << endl;}
    }
};

int main()
{
    int n,m;cin>>n>>m;
    Graph mygraph(n);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;cin>>a>>b>>c;
        mygraph.addEdge(a-1,b-1,c);
    }
    mygraph.dijkstra(0);
    return 0;
}