堆优化Dijkstra算法

堆优化Dijkstra算法针对Dijkstra算法中的第1步用堆进行优化，使用时需满足两个条件：

(1)边权没有负值

(2)稀疏图

存储结构采用邻接链表，n为顶点数，m为边数

int value[m], next[m], head[n], edge[m], d;

memset(head, -1, sizeof(head));

若源结点为顶点s，dis[i]标示源结点s到顶点i的最短距离（初始化dis[s]为0，其他为0x3f3f3f3f），vis[i]标示顶点i是否已被访问（0是未访问，1是已访问，初始化为全0）

int dis[n], vis[n];

堆优化Dijkstra算法基于贪心，算法流程如下：

(1)建立小顶堆，堆中元素为pair类型，其first为dis[j]，second为j，取出堆顶，其为距离源结点s最短的顶点p（dis[p]为最短），如果p已被访问（vis[p]为1）需要舍弃

(2)标记p为已访问（vis[p]标记为1），用顶点p更新其可达顶点j的dis[j]（如果dis[p] + edge[i] < dis[j]，则用dis[p] + edge[i]更新dis[j]，其中edge[i]为顶点p到顶点j的边权），然后将pair类型{dis[j], j}入堆

(3)循环1、2步，不断取出堆顶直到堆空

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

while (!heap.empty()) {
    auto t = heap.top();
    heap.pop();
    int p = t.second;

    if (vis[p]) continue;

    vis[p] = 1;
    for (int i = head[p]; i != -1; i = next[i]) {
        int j = value[i];
        if (dis[p] + edge[i] < dis[j]) {
            dis[j] = dis[p] + edge[i];
            heap.push({dis[j], j});
        }
    }
}

算法结束时，dis[i]存储源结点s到顶点i的最短距离，0x3f3f3f3f表明不可达

注解：

(1)小顶堆heap中的pair为{dis[j], j}，则先按dis[j]升序排序，相等时再按j升序排序

(2)heap中的顶点不全是未访问，无法通过在heap中判断是否访问（dis[j]更新后顶点j入堆，之前可能有j旧值并未删除，后面j新值在堆顶被取出并标记为已访问后，j旧值仍然在堆中），故而第1步，如果p已被访问需要舍弃

当然，值得一提的是，heap中顶点j的数据可能会存在多个，不过并不影响

(3)堆优化Dijkstra算法第2步，本应是用顶点t更新其可达、未访问顶点j的dis[j]，可实现时更新操作却循环了所有可达顶点（这里面有已访问顶点），这是由于没有负权边，已访问顶点j的dis[j]不会被更新，即使循环到也无妨

(4)堆优化Dijkstra算法适用于稀疏图（稀疏图定义参照图的存储结构）

---