各种寻找~~你脑子里~~最短路的算法

Floyd 算法

求多源最短路，可以正确处理有向图或负权的多源最短路径问题。使用邻接矩阵记录图。时间复杂度为 $O(N^3)$ ，空间复杂度为 $O(N^2)$ 。

Floyd 的原理是动态规划。在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。

void floyd(int n)
{
	for(int k=1;k<=n;k++)  
		for(int i=1;i<=n;i++)  
			for(int j=1;j<=n;j++)  
				if(e[i][j]>e[i][k]+e[k][j])  
					e[i][j]=e[i][k]+e[k][j];
	return;
}

实现方法：最开始只允许经过 $1$ 号顶点进行中转，接下来只允许经过 $1$ 和 $2$ 号顶点进行中转，直至允许经过 $1-n$ 号所有顶点进行中转，求最短路径。用一句话概括就是：从 $i$ 号顶点到 $j$ 号顶点只经过前 $k$ 号点的最短路程。

SPFA 算法

SPFA 算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。

通过维护一个队列，使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点，从而大大减少了重复的操作次数。SPFA 可以用于存在负数边权的图。

算法时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别。在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度仅为 $O(E)$ 。另一方面，存在这样的例子，使得每一个节点都被入队 $V-1$ 次，此时算法退化为 Bellman-ford 算法，其时间复杂度为 $O(VE)$ 。

综上，时间复杂度是 $O(kE)$ ，其中 k 可看作常数**。注意这个结论不算正确**。

SPFA 在稀疏图中表现良好。但是在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的 Dijkstra 算法，以及它的使用堆优化的版本。通常的 SPFA 算法在一类网格图、菊花图中的表现不尽如人意。

下面的模板用链式前向星存图。

queue<int>q;
void spfa(int x)
{
	memset(dis,0x3f,sizeof(dis));
	q.push(x);dis[x]=0;vis[x]=1;
	while(!q.empty())
	{
		int now=q.front();q.pop();
		vis[now]=0;
		for(int i=head[now];i;i=e[i].next) 
		{
			int to=e[i].end;
          	if(dis[to]>dis[now]+e[i].len)
          	{
          		dis[to]=dis[now]+e[i].len;
				if(!vis[to])
					q.push(to),vis[to]=1;
			}
		}
	}
	return;
}

实现方法：建立一个队列，初始时队列里只有起始点。再使用 dis[] 数组记录起始点到所有点的最短路径（初始化为极大值，起始点为 $0$ ）。然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列。重复执行直到队列为空。

此外，SPFA 算法还可以判断图中是否有负权环，即一个点入队次数超过 N。

也可求最长路（边权取反最短路 = 最长路）。

dijkstra 算法

求单源、无负权的最短路。时效性较好，时间复杂度为 $O(n^2)$ 。是一种经典的基于贪心的单源最短路算法。

它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

借助优先队列作为辅助数据结构，算法时间复杂度则为 $O((n+m)logn)$ 。

下面的模板用链式前向星存图。

struct node{int name,dis;};
bool operator<(node a,node b){return a.dis>b.dis;}
priority_queue<node>q;
void dijkstra(int x)
{
	memset(dis,0x3f,sizeof(dis));
	dis[x]=0;
	q.push((node){x,dis[x]});
	while(!q.empty())
	{
		int now=q.top().name;
		q.pop();
		if(vis[now])
			continue; 
		for(int i=head[now];i;i=e[i].next) 
		{
			int to=e[i].end;
          	if(dis[to]>dis[now]+e[i].len)
          	{
          		dis[to]=dis[now]+e[i].len;
				q.push((node){to,dis[to]});
			}
		}
		vis[now]=1;
	}
	return;
}