引入¶

二叉树的BFS层序遍历

Dijkstra 算法框架¶

首先，我们先看一下 Dijkstra 算法的签名：

class State {
    // 图节点的 id
    int id;
    // 从 start 节点到当前节点的距离
    int distFromStart;

public:
    State(int id, int distFromStart) {
        this->id = id;
        this->distFromStart = distFromStart;
    }
};

标准的 Dijkstra 算法会把从起点 start 到所有其他节点的最短路径都算出来。

当然，如果你的需求只是计算从起点 start 到某一个终点 end 的最短路径，那么在标准 Dijkstra 算法上稍作修改就可以更高效地完成这个需求，这个我们后面再说。

state类记录状态和距离¶

其次，我们也需要一个 State 类来辅助算法的运行：

class State {
    // 图节点的 id
    int id;
    // 从 start 节点到当前节点的距离
    int distFromStart;

public:
    State(int id, int distFromStart) {
        this->id = id;
        this->distFromStart = distFromStart;
    }
};

类似刚才二叉树的层序遍历，我们也需要用 State 类记录一些额外信息，也就是使用 distFromStart 变量记录从起点 start 到当前这个节点的距离。

visted数组防止回头路¶

刚才说普通 BFS 算法中，根据 BFS 的逻辑和无权图的特点，第一次遇到某个节点所走的步数就是最短距离，所以用一个 visited 数组防止走回头路，每个节点只会经过一次。

distTo数组记录最短路径权重¶

优先队列distFromStart优化算法¶

Dijkstra 可以理解成一个带 dp table（或者说备忘录）的 BFS 算法¶

伪代码如下：

// 返回节点 from 到节点 to 之间的边的权重
int weight(int from, int to);

// 输入节点 s 返回 s 的相邻节点
vector<int> adj(int s);

// 输入一幅图和一个起点 start，计算 start 到其他节点的最短距离
vector<int> dijkstra(int start, vector<int> graph[]) {
    // 图中节点的个数
    int V = graph.size();
    // 记录最短路径的权重，你可以理解为 dp table
    // 定义：distTo[i] 的值就是节点 start 到达节点 i 的最短路径权重
    int distTo[V];
    // 求最小值，所以 dp table 初始化为正无穷
    memset(distTo, INT_MAX, sizeof(distTo));
    // base case，start 到 start 的最短距离就是 0
    distTo[start] = 0;

    // 优先级队列，distFromStart 较小的排在前面
    priority_queue<State, vector<State>, decltype(&comparator)> pq(&comparator);

    // 从起点 start 开始进行 BFS
    pq.push(State(start, 0));

    while (!pq.empty()) {
        State curState = pq.top();
        pq.pop();
        int curNodeID = curState.id;
        int curDistFromStart = curState.distFromStart;

        if (curDistFromStart > distTo[curNodeID]) {
            // 已经有一条更短的路径到达 curNode 节点了
            continue;
        }
        // 将 curNode 的相邻节点装入队列
        for (int nextNodeID: adj(curNodeID)) {
            // 看看从 curNode 达到 nextNode 的距离是否会更短
            int distToNextNode = distTo[curNodeID] + weight(curNodeID, nextNodeID);
            if (distTo[nextNodeID] > distToNextNode) {
                // 更新 dp table
                distTo[nextNodeID] = distToNextNode;
                // 将这个节点以及距离放入队列
                pq.push(State(nextNodeID, distToNextNode));
            }
        }
    }
    vector<int> result;
    for (int i = 0; i < V; i++) {
        result.push_back(distTo[i]);
    }
    return result;
}