dijkstra算法 c++示范

Dijkstra算法是一种用于寻找图中两点之间最短路径的经典算法，它适用于带权重的无负权边的图。以下是Dijkstra算法的一个基本C++示例，使用邻接矩阵表示图：

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

// 定义距离结构
struct DistanceNode {
    int node;
    int distance;
};

bool compareNodes(DistanceNode a, DistanceNode b) {
    return a.distance < b.distance;
}

void dijkstra(vector<vector<int>>& graph, int start) {
    vector<int> distances(graph.size(), INT_MAX);
    distances[start] = 0; // 初始化起始节点的距离为0

    priority_queue<DistanceNode, vector<DistanceNode>, decltype(compareNodes)> pq(compareNodes);

    for (int i = 0; i < graph.size(); i++) {
        DistanceNode currentNode;
        currentNode.node = -1; // 标记已处理节点

        while (!pq.empty() && currentNode.node == -1) {
            currentNode = pq.top();
            pq.pop();

            if (currentNode.distance < distances[currentNode.node]) continue; // 如果已经更新过更小的距离，则忽略

            for (int neighbor : graph[currentNode.node]) { // 遍历邻居
                int newDistance = currentNode.distance + graph[currentNode.node][neighbor];

                if (newDistance < distances[neighbor]) {
                    distances[neighbor] = newDistance;
                    pq.push({neighbor, newDistance}); // 更新邻接节点距离并入队列
                }
            }
        }
    }

    // 输出结果
    for (int i = 0; i < distances.size(); i++) {
        cout << "从" << start << "到" << i << "的最短距离是：" << distances[i] << endl;
    }
}

int main() {
    // 示例图（邻接矩阵表示）
    vector<vector<int>> graph = {{0, 4, 0, 0, 0},
                                  {4, 0, 8, 0, 0},
                                  {0, 8, 0, 7, 0},
                                  {0, 0, 7, 0, 9},
                                  {0, 0, 0, 9, 0}};

    dijkstra(graph, 0); // 从节点0开始搜索
    return 0;
}

这个示例展示了如何使用优先队列来实现Dijkstra算法，并找出给定起点(start)到其他所有节点的最短路径。