最短路

跑图？？

最短路

最短路问题，我们可以根据下面两种方式来分类

第一种，按是否有边权。对于无边权的有向图，求最短路，我们用 BFS 。对于有边权的图，特殊的图可以采用 01BFS 求解，对于一般的图，将在后文详细讨论。

第二种，根据“源”和“汇”的关系。分为单源单汇、单源多汇、多源单汇、多源多汇。 在实际算法中，我们其实不太关心单汇还是多汇。哦，原来只是因为老师都是简单讲讲。

Floyd

复杂度：

顺序很重要！！！别的就不管了

枚举 是用来更新的点， 是起点， 是终点。

for(int k = 1; k <= n; ++k)
	for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            a[i][j] = min(a[i][j], a[i][k] + a[k][j]);

Dijkstra

每次从 「未求出最短路径的点」中 取出 距离起点 最小路径的点，以这个点为桥梁 刷新「未求出最短路径的点」的距离

#include <bits/stdc++.h>
#define N 10007
using namespace std;

int dis[N];

bool vis[N];

int main() {
	memset(vis, 0, sizeof(vis));
	memset(dis, 0x3f, sizeof(dis));
	cin >> n >> m >> s;
	// 读入存图 略 
	dis[s] = 0;
	for(int i = 1; i <= n; ++i){
		//find the min dis
		int nwmn = 1e9, u = 0;
		for(int j = 1; j <= n; ++j)
			if(!vis[j] && dis[j] < nwmn){
				nwmn = dis[j]; u = j;
			}
		vis[u] = 1;
		for(int j = hd[u], v; j; j = e[j].nxt){
			dis[v = e[i].to] = min(dis[v], dis[u] + e[j].w);
		}
	}
    return 0;
}

SPFA

SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法，它是Bellman-ford的队列优化，它是一种十分高效的最短路算法。

很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。SPFA的复杂度大约是 O(kE) , 是每个点的平均进队次数(一般的， 是一个常数，在稀疏图中小于2)。

但是，SPFA算法稳定性较差，在稠密图中SPFA算法时间复杂度会退化。

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

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

#include <bits/stdc++.h>
#define N 10007
using namespace std;

int dis[N];

bool vis[N];

queue<int> q;

int main() {
	memset(vis, 0, sizeof(vis));
	memset(dis, 0x3f, sizeof(dis));
	cin >> n >> m >> s;
	// 读入存图 略 
	dis[s] = 0; q.push(s); vis[s] = 1;
	while(!q.empty()){
		int u = q.front();
		q.pop(); vis[u] = 0;
		for(int i = hd[u], v; i; i = e[i].nxt){
			if(dis[v = e[i].to] > dis[u] + e[i].w){
				dis[v] = dis[u] + e[i].w;
				if(!vis[v]) {q.push(v); vis[v] = 1;}
			}
		}
	}
	return 0;
}