最短路问题是什么

给定一个有向带权图和两个点s,t，求一条路径从s到t，并且这条路径的边权和最小。这个问题称为最短路问题

最基础的操作——松弛

设dis[s][t]表示从s到t最短路的边权和，那么它一定满足一个性质：对于任意k，dis[s][t]<=dis[s][k]+dis[k][t]，否则显然从s走到k再走到t更优。

如果dis[s][t]>dis[s][k]+dis[k][t]，则把dis[s][t]更新为dis[s][k]+dis[k][t]，这个操作称为用点k对s,t进行松弛。

松弛是所有最短路算法的基础。

算法1 Floyd

Floyd可以用来求任意两点的最短路。

假设我们已经求出了从s到t，经过的点只可能是1..k-1中的一些点，我们考虑把k加进去，也就是用k对s,t进行松弛。这样从s到t经过的点就可能是1..k中的点。

一开始如果s=t则dis[s][t]=0，否则如果s到t有边则dis[s][t]为边权否则为\infty∞

枚举k从1到n，s,t显然也要从1到n，这样就能求出任意两点间的最短路了。

注意k要在外层循环

时间复杂度稳定的O(n^3)O(n3)

代码只需要5行。（甚至可以更低）

算法2 Bellman-Ford

Bellman-Ford是用来求一个点s到所有点的最短路的。

如果从s到t有最短路，那么经过的边数一定可以<=n-1。

证明：假设边数可以>=n，那么路径中肯定经过了重复的点，那就出现了一个环。

如果环权>=0，显然可以把路径中这个环删掉。

否则？那么我们就找到了负权环。

（对于Floyd判断负权环，只需考虑是否有s满足dis[s][s]<0）

假设我们已经求出了经过从s经过不超过k-1条边到t的最短路。

然后对于每条边u,vu,v，可以直接定义dis[u][v]是这条边的边权（因为我们不需要算出u到v的最短路），对每条边松弛一次就可以了。

松弛完n-1次以后，如果还能松弛，那么就找到负权环了。

一个基本上没什么用的优化，在一次对每条边的松弛中，如果每次松弛都没更新，那就不用松弛了。

时间复杂度O(nm)O(nm)。

算法3 SPFA

当s到一个点的最短路更新了，这个点才用再去更新其他点。

我们用一个数据结构存准备拿来更新其它点的点。

每次从这里面取出一个，然后更新其它点，

如果一个点被更新了，就放进数据结构。

这就要分成两种情况（优先队列不考虑）

1. 数据结构是队列（通常情况）

这样就是BFS的版本。

在把一个点放进队列的时候，如果它已经在队列里面了，就不放了(qwq)

由于一个点第i次入队的时候（一开始s入队算第0次），从s到它最短路的长度至少是i，如果一个点入队了n次及以上，那么就出现了负权环。

时间复杂度不稳定，可以写作O(km)O(km)，其中k是每个点的平均入队次数。

但是实际上，这个复杂度实际上是O(nm)O(nm)。不光是出现负权环的情况，正权图也是可以的。

具体的卡法：假设100000个点。

把点排成10行10000列，连成网格图，其中横边边权比较大且随机，竖边边权为1。

从左上开始跑最短路。

关于卡SPFA？不卡是情分，卡是本分。

连noi的赛场上 也是卡了SPFA

2. 数据结构是栈

这个就是DFS的版本。

当然可以用系统栈。

当把一个点更新后，立刻用这个点开始更新其它点，如果从一个点更新到了它自己，那么显然出现了负权环。

复杂度实际上是指数级的。

卡法？ 

以这样的图为基础让他从1到3往后走，然后到2，再到3，发现前面的路要重走一遍

就能卡到指数级了。

算法4 Dijkstra

Dijkstra可以用在边权非负的情况求出s到所有点的最短路。

我们对每个点标记它是否已经更新了其它点。

每次选出还没有用来更新其它点中目前最短路最小的点，拿来更新其它点。

这东西为什么正确呢？

当我选出一个点的时候，它已经被之前选出来的点更新过了，准备拿来更新其它点。

显然它不会再被另外的点更新了。

那么这个点就已经得到了最短路。

如果直接选择，复杂度为O(n^2)O(n2)。

优化

用优先队列存最短路和对应的点。

但是优先队列很难解决对最短路的更新。

方案1： 更新了再次扔进优先队列，新的一定会在原来的之间出队。 那原来的出队的时候，由于已经更新过这个点，就跳过。时间复杂度O(m \log m)O(mlogm)

方案2： 用支持修改元素值的优先队列 例如手写个什么左偏树之类的。时间复杂度O(m\log n)O(mlogn)，也可以手写斐波那契堆/直接用pbds里的priority_queue，复杂度O(n\log n+m)O(nlogn+m)