最短路算法合集

~~noip快要考了发现spfa不会打的我~~决定来总结一下最短路算法。

dijkstra

dijkstra基于最短路的最优子结构性质。设(s(u, v))表示u到v的最短路，若k是它们最短路L上的点，那么(s(u, k)+s(k, v)=s(u, v))（首先(s(u, k)+s(k, v)>=s(u, v))，并且如果(s(u, k)+s(k, v)>s(u, v))，那么u到v的最短路一定不经过k，画个图就明白了）。设源点为S，当前松弛点为P，则(s(S, P))必定对于某一个与P相邻的节点Q满足(s(S,P)=s(S,Q)+s(Q,P))成立。所以算法就成立了（前提是没有负权边，不然曾经的点的最短路就不是真正的最短路，而整个算法是建立在求出所有点的正确的最短路上的）。注意dijkstra中，由于最多松驰m次，因此最多将堆中点的权值减去m次，用普通堆的复杂度是(O(mlogm)=O(mlogn))，而用斐波那契堆，可以搁置某些减权操作，使得松驰的总时间复杂度变成(O(nlogn))，不过我并不会0.0。

（貌似正确的）程序：

int dis[maxn*2], vis[maxn];
struct cmp{
	bool operator()(int x, int y){
		return dis[x]>dis[y]; }
};
priority_queue<int, vector<int>, cmp> q;
void dijkstra(int src){
	memset(dis, 0x3f, sizeof(dis)); dis[src]=0;
	int u, v; q.push(src);
	for (int i=1; i<=n; ++i){  //出n个点 
		while (vis[u=q.top()]) q.pop(); vis[u]=1;
		for (int j=fir[u]; j; j=e[j].nxt){
			v=e[j].to;
			if (dis[u]+e[j].v<dis[v])
				dis[v]=dis[u]+e[j].v, q.push(v);
		}
	}
}

这样写是错的！这种情况下stl无法正确维护优先队列。所以必须要用(greater<int>+pair<int, int>)/(struct)。

不过为了更简洁，就这样吧……

spfa

首先要说明bellman-ford算法的正确性。只要(s(u, k)+s(k, v)>s(u, v))成立，那么对所有结点都松弛n次，最短路就一定可以被求出来（最短路的长<=n）。spfa就是只考虑松弛后的结点的一个玄学优化，至于为什么对？！咳咳这是经验公式

floyd

floyd的本质是动态规划，至于为什么把k放在外层，是因为k是动态规划状压的状态。若用(f[k][i][j])表示可以通过1到k中结点的ij最短路路径，(f[k][i][j]=min(f[k-1][i][j], f[k-1][i][k]+f[k-1][k][j]))，而最外面一层空间被省略了，因为状态里面有k的通通不会更新。所以能保证正确性。

也可以从矩阵的角度来理解。考虑求点对之间走x步的方案数，其实相当于x个邻接矩阵相乘。

如何证明呢？设现在的情况是走x步的矩阵X和邻接矩阵Y相乘。那么X的第i行第j列，就表示从i到j的方案数。Y的第i行第j列表示从i到j的连通性。那么，新的从i到j的方案数，事实上就是选一个点k多走一步的方案数。因此，X的第i行乘上Y的第j列，表示的就是从i到k再到j的方案数。时间复杂度(O(n^4))

由于floyd要求的是最短路，我们发现可以用矩阵快速幂优化到(O(n^3log n))！！！欸欸欸，floyd不是(n^3)的嘛……

这是因为Floyd只乘了矩阵的第k行，乘了n次。