Dijkstra学习笔记

介绍

这个算法适用于非负权图中求单源最短路（一个顶点到其他所有顶点的最短路），有着稳定优秀的时间复杂度，暴力Dij时间复杂度为 $O(n^2)$ ，堆优后为 $O(mlogn)$ 。事实上 $m$ 和 $n^2$ 是同阶的，不过一般情况下 $m$ 远小于 $n^2$ ，这种图被称为稀疏图；而 $m$ 相对较大的图则被称为稠密图，这种情况下暴力Dij可能要比堆优Dij更优。

该算法主要思想是将所有结点分为两个集合：已确定最短路径长度 $\rm d[x]$ 的与没确定的。最开始前面的集合中只有起点 $s$ 。然后将前一个集合中的所有出边进行松弛，在后面的集合中选出最短路 $\rm d[x]$ 最小的结点并标记访问，加入前面的集合中。直到所有节点都访问过即后一个集合没有元素，算法结束。

可以通过反向建图（将每条有向边的起点与终点互换）来求所有点到达一个固定点的最短路，只需要反向建图之后以到达的点为起点进行Dij。

实现

存图

这里使用邻接表进行存图

const int MAXN = 100000 + 5;
const int MAXM = 200000 + 5;

struct Edge { //用来存每条边的终点，下一条边的边号，权值
    int e, next, d;
}ed[MAXM];

int first[MAXN], en; //first数组为以 i 为起点的第一条边的边号

void add_edge(int s, int e, int d) { //单向边加边
    en++;
    ed[en].next = first[s];//第en条边的下一条边更改为以s为起点的第一条边
    first[s] = en;         //将以s为起点的第一条边改为en
    ed[en].e = e;          //终点
    ed[en].d = d;          //边权
}

Dijkstra

int d[MAXN];     //保存从起点s到i的最短路径长度
bool vis[MAXN];  //布尔类型数组用来记录结点i是否被访问
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > q;
//含有两个元素的大根堆。由于默认先比较前一项，所以前一项为权值，后一项为结点编号
inline void Dijkstra(int s) {    //s为起点编号
    memset(d,0x3f,sizeof(d));   //0x3f3f3f3f可视为无限大，可以相加也可以使用memset进行填充
    d[s] = 0;                  //将起点到起点的距离初始化为0
    q.push(mark_pair(0, s));  //将结点s存入堆中
    while(!q.empty()) {
       	int now = q.top().second;  q.pop();  //取出优先队列中的第一个点
        if(!vis[now]) {
            vis[now] = true;
            for(int i = first[now]; i; i = ed[i].next)  {  //枚举出边
            	int e = ed[i].e;
                if(d[e] > d[now] + ed[i].d) {   //松弛
                    d[e] = d[now] + ed[i].d;
                    q.push(make_pair(d[e], e);  //如果出边所连另一个结点被访问且没被加入堆，将其加入
                }
            }
        }
    }
}