白书上的dijkstra+堆优化/dijkstra的一些性质

模板

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int maxn=11111;
const int maxm=11111;
const int INF=1e9;

struct Edge{
    int from,to,dist;
};

struct HeapNode{
    int d,u;
    bool operator<(const HeapNode& rhs) const{
        return d>rhs.d;
    }
};

struct Dijkstra{
    int n,m;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool done[maxn];
    int d[maxn];
    int p[maxn];

    void init(int n){
        this->n=n;
        for (int i=0;i<n;i++) G[i].clear();
        edges.clear();
    }

    void addedge(int from,int to,int dist){
        edges.push_back((Edge){from,to,dist});
        m=edges.size();
        G[from].push_back(m-1);
    }

    void dijkstra(int s){
        priority_queue<HeapNode>que;
        for (int i=0;i<n;i++) d[i]=INF;
        d[s]=0;
        memset(done,0,sizeof(done));
        que.push((HeapNode){0,s});
        while (!que.empty()){
            HeapNode x=que.top();
            que.pop();
            int u=x.u;
            if (done[u]) continue;
            done[u]=true;
            for (int i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if (d[e.to]>d[u]+e.dist){
                    d[e.to]=d[u]+e.dist;
                    p[e.to]=G[u][i];//p[e.to]=e.from;
                    que.push((HeapNode){d[e.to],e.to});
                }
            }
        }

    }
};

性质

路径统计

用dijkstra还可以枚举两点间的所有最短路，以及统计最短路的条数。枚举最短路的方法是这样的：先求出所有点到目标点的最短路长度d[i],然后从起点开始出发行走，但只沿着d[i]=d[j]+w(i,j)的边走。不难证明，如果一直顺着这样的边走，走到目标点时，走出的一定是最短路;反过来，只要有一次走的不是这样的边，走到目标点时，走出的一定不是最短路。有了这样的结论，计数也不是难事，令f[i]表示从i到目标点的最短路的条数，则f[i]=sum{ f[j] | f[i]=d[j]+w(i,j) },边界条件为终点的f值等于1。

最短路树

用dijkstra算法可以求出单源最短路树，方法是在发现d[i]+w(i,j)<d[j]时除了更新d[j]之外还要设置p[i]=j。这样，把p看成是父指针，则所有点形成了一棵树。这样，要从起点出发沿最短路走到任意其他点，只需要顺着树上的边走即可。前面的dijkstra算法的代码已经求出了p数组。