《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（41）风火轮寻径术 - Dijkstra最短路径（优先队列）

《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（41）风火轮寻径术 - Dijkstra最短路径（优先队列）

哪吒在数据修仙界中继续他的修炼之旅。这一次，他来到了一片神秘的风火轮平原，平原上有一座巨大的风火轮，轮身闪烁着神秘的光芒。平原的入口处有一块巨大的石碑，上面刻着一行文字：“欲破此原，需以风火轮之力，寻径术，优先队列定乾坤。”

哪吒定睛一看，石碑上还有一行小字：“图[[2, 1, 4], [1, 3, 2], [3, 4, 1]]中，节点1到节点4的最短路径为3。”哪吒心中一动，他知道这是一道关于 Dijkstra 最短路径的难题，需要通过优先队列优化的 Dijkstra 算法找到图中两点间的最短路径。

暴力解法：风火轮的初次尝试

哪吒心想：“要找到最短路径，我可以尝试所有可能的路径。”他催动风火轮之力，从起点开始，逐个节点遍历，记录每条路径的长度，试图找到最短路径。

int dijkstra(vector<vector<int>>& graph, int start, int end) {
   
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;
    for (int i = 0; i < n - 1; ++i) {
   
        for (int u = 0; u < n; ++u) {
   
            if (dist[u] == INT_MAX) continue;
            for (auto& edge : graph[u]) {
   
                int v = edge[0];
                int weight = edge[1];
                if (dist[v] > dist[u] + weight) {
   
                    dist[v] = dist[u] + weight;
                }
            }
        }
    }
    return dist[end];
}

哪吒成功地找到了最短路径，但风火轮的光芒却黯淡了下来。他意识到，这种方法虽然可行，但效率低下，尤其是当图很大时，灵力消耗巨大。

C++语法点

在C++中，Dijkstra算法涉及到优先队列和图的表示。以下是一些重要特性：

• 优先队列：

  • 使用priority_queue来存储节点和当前距离。
  • 常用操作：
    • push：将节点和距离加入队列。
    • top：获取队列中距离最小的节点。
    • pop：移除队列中距离最小的节点。

• 图的表示：

  • 使用邻接表表示图，每个节点的邻接节点和边权重存储在一个列表中。

高阶优化：优先队列的智慧

哪吒元神中突然浮现金色铭文——「风火轮寻径术，优先队列定乾坤」。他意识到，可以通过优先队列优化 Dijkstra 算法，每次选择距离最小的节点进行扩展。

哪吒决定使用优先队列，从起点开始，每次取出距离最小的节点，更新其邻接节点的距离。通过这种方式，他成功地找到了最短路径，而且灵力消耗大幅减少。

int dijkstra(vector<vector<pair<int, int