【图论】无堆优化 Dijkstra 和 SPFA

Pre：链式前向星

链式前向星是链表方式实现的邻接表存图，继承了邻接表的时间效率较快，空间占用较少的优势，实现简单，惟因实现上是对每条边进行编号，因而对点排序十分不便。

实现

记录了起点 \(u\) 和终点 \(v\) 的略经修改的实现。

struct edge{ // 存边
	int u,v,w,next;
}e[ ];

void add(int u,int v,int w){ // 连 (u,v)
	e[++k] = {u,v,w,pre[u]};
	pre[u] = k;
	return ;
}

for (int i = pre[n]; i != 0 ; i = pre[i].next) { // 遍历节点 n 的所有边

}

Dijkstra 算法

Dijkstra 算法适合解决 边权非负 的 单源最短路 问题。

具体地，Dijkstra 的实现可以被描述为以下内容。

实现

令 \(\text{dis}(x)\) 表示源点 \(s\) 到图上一点 \(x\) 的最短路径长度。

如果我们以点 \(s\) 为源点，根据 \(\text{dis}\) 的定义可以得到 \(\text{dis}(s) = 0\)。需要注意的是，\(\text{dis}\) 是一个过程量，为了求取最值需要钦定 \(\text{dis}(u \in V \land u \ne s) = +\infty\)。

接下来将 \(V\) 分割为两个集合，已确定最短路点集 \(S\) 和未确定最短路点集 \(T\)。初始 \(S = \left\{s\right\}\)。

循环进行以下操作直至 \(T = \varnothing\)：

• 若 \(\exists n,\text{dis}(n) = \min\limits_{i \in T} \text{dis}(i),\) 将 \(n\) 加入 \(S\)；
• 松弛所有属于 \(S\) 的结点的所有出边（更新 \(\text{dis}\) 的值）

无堆优化 参考实现

\(\Theta(n^2)\) 链式前向星的实现，其中 \(n\) 表示节点数量，\(d_i\) 表示节点 \(i\) 的 \(\text{dis}\)。

bool vis[ ];
int d[ ];
int pre[ ];
int k = 0;
// <--- 链式前向星
struct edge{
	int u,v,l,next;
}a[];

void add(int u,int v,int l){
	a[++k] = {u,v,l,pre[u]};
	pre[u] = k;
	return ;
}
// --->

// 初始化
memset(d,0x3f,sizeof(d));
d[x] = 0;

for(int i = 1; i <= n; i ++) {
    // 1.选取 dis 最小的点
	int mi = -1;
	for(int j = 1; j <= n; j ++) {
		if(!vis[j] && (mi == -1 || d[j] < d[mi])) {
			mi = j; 
		}
	}
	vis[mi] = true; // 加入集合
    // 2. 松弛
	for(int j = pre[mi]; j != 0; j = a[j].next) {
		if(!vis[a[j].v] && d[mi] + a[j].l < d[a[j].v]) {
			d[a[j].v] = d[mi] + a[j].l;
		}
	}
}

SPFA

Shortest Path Faster Algorithm，习惯上称 Bellman-Ford 算法的队列优化。

SPFA 适用于在负边权的图上跑最短路，由于好写好理解深受青睐，但由于有“SPFA 已死”的断论存在，非负边权图上跑最短路的题目中，出题人们已经设计了很多卡 SPFA 的 hack 方案，所以在实现时要和 Dijkstra 多作考量。

与朴素 Bellman-Ford 算法的实现不同的是，我们采用队列维护所有「有可能会引起松弛操作的节点」，即「上次被松弛节点」，来跑与它们相连的边，来规避掉冗余的松弛操作，节省时间。

无堆优化 参考实现

链式前向星存图，可读性较低。

int d[ ];
bool vis[ ];
int pre[ ];
int k = 0;
queue<int> q;
 
struct edge{
    int u,v,l,next;
}a[ ];
 
void add(int u,int v,int l){
    a[++k] = {u,v,l,pre[u]};
    pre[u] = k;
    return ;
}
memset(d,0x3f,sizeof(d));
d[1] = 0;
q.push(1);
vis[1] = true;
while(!q.empty()){ 
    for(int i = pre[q.front()];i != 0;i = a[i].next){
        if(d[q.front()] + a[i].l < d[a[i].v]){
            d[a[i].v] = d[q.front()] + a[i].l;
            if(!vis[a[i].v])q.push(a[i].v),vis[a[i].v] = true;
        }
    }
    vis[q.front()] = false;
    q.pop();
}