Floyd 算法

Floyd 算法，号称五行算法，确实代码简洁，但是也有不足，就是跑得慢
Floyd算法时间复杂度为O(n^3)
基本思路也很简洁，采用的是最基本的动归：
有dp数组：dp[k][i][j]表示：使用前k号点作为中间媒介时，点i到点j之间的最短路径长度
则我们能够得到状态转移方程：
dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j])
类似01背包，这里可以在空间上做一定的优化：

我们可以注意到比如第i个阶段第j个状态它是从第i-1个阶段第j个状态前面转移过来的，所以我们完全只用一个一维的dp数组就够了，即我们只需要保存上一个阶段的所有状态，当前阶段的状态可以从这个数组中转移并储存，而不影响别的状态的转移（比如我们计算得到了当前阶段的第j个状态的值，我们覆盖掉保存的上一个阶段第j个状态的值，这不会影响后面状态的转移，因为后面的状态不会再用到这个值了）
但是我们要注意一点，前面已经说了，当前阶段的状态是从上一个阶段转移过来的，如果我们用一维dp数组，我们还是按顺序转移，即如下所示的转移过程：

那么有：
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
感性的直观认识即为：

对于第1个中间点k1，计算以k1作为中间点时，所有点两两之间的最小距离；对于第2个中间点k2，计算以k2作为中间点时，所有点两两之间的最小距离，如果这个距离比之前的小，就更新d[i][j]的值……如此遍历所有中间点k后，所有d[i][j]都更新到最小值。
代码为：

 for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(e[i][j]>e[i][k]+e[k][j])
                     e[i][j]=e[i][k]+e[k][j];

Dijstra 算法

Dijstra的内核是贪心，属于动归的一种子集
每次在剩余节点中找到离起点最近的节点放到队列中，并且用来更新剩下的节点的距离，再将它标记上，表示已经找到它的最短路径，不再更新它了
这是基于：到一个节点的最短路径必然会经过比它离起点更近的节点，而如果一个节点的当前距离值比任何剩余节点都小，那么当前的距离值一定是最小的。
为了做到这一点，我们采用优先队列来实现

#include<iostream>
#include<queue>
#include<algorithm>
#define MAX 200
using namespace std;
struct Edge
{
	int to; int next; int w;
}edges[MAX];
int head[MAX];

struct Node
{
	int now; int weight;
};
//降序是相反
bool operator < (Node a, Node b) {
	return a.weight > b.weight;
}

priority_queue<Node> Q;
int cnt = 0, d[MAX];

void init() {
	memset(head, -1, sizeof(head));
	while (!Q.empty())Q.pop();
	memset(d, (int)(1e9+7), sizeof(d));
	cnt = 0;
}
void add(int from, int to, int weight) {
	edges[cnt].w = weight;
	edges[cnt].to = to;
	edges[cnt].next = head[from];
	head[from] = cnt++;
}
int main(){
	int T; cin >> T;
	while (T--) {
		init();
		int A, B, n; cin >> A >> B >> n;
		for (int i = 0; i < n; i++) {
			int a, b, w; cin >> a >> b >> w;
			add(a, b, w);
		}
		Q.push({ A,0 });
		while (!Q.empty()) {
			Node cur = Q.top();
			Q.pop();
			if (d[cur.now] < cur.weight)continue;
			for (int i = head[cur.now]; ~i; i = edges[i].next) {
				int to = edges[i].to;
				if (d[to] > cur.weight + edges[i].w)
					d[to] = cur.weight + edges[i].w, Q.push({ to,d[to] });
			}
		}
		cout << d[B] << endl;
	}
}

Spfa 算法

dijstra的局限性在于不能处理负权，因为采用的是贪心的方法
所以Bellman-Ford采用了对所有节点进行一次松弛操作
spfa是bellman-ford的队列优化版本，不需要将所有边拿来松弛，只有那些已经确定了最短路径的点所连出去的边才是有效的

bool inq[MAX_N];
void SPFA(int s)
{
	//初始化距离d，队列，inq队列标志 
	queue<int> que;
	memset(d, 0x3f, sizeof(d));
	d[s] = 0;
	memset(inq, 0, sizeof(inq));
	que.push(s);
	while(que.size())
	{
		int u = que.front();	que.pop();
		//清除标志 
		inq[u] = false;			
		//对每一条邻边松弛操作 
		for(int i = first[u]; i != -1; i = next[i])		 
			if(d[e[i].u] + e[i].w < d[e[i].v])
			{
				d[e[i].v] = d[e[i].u] + e[i].w;
				if(!inq[e[i].v])
				{
					inq[e[i].v] = true;
					que.push(e[i].v);
				}
			}
	}
}

和dijstra的最大区别在于，spfa是对所有已知点连出去的边进行了松弛
即，
该算法能够保证每更新一次都能确定一个节点的最短路，但与dijkstra不同的是，并不知道是那个节点的最短路被确定了，只是知道比上次多确定一个，这样进行n-1次更新后所有节点的最短路都确定了（源点的距离本来就是确定的）

Bellman-Ford判负环：

如果循环执行了n-1次，那就说明有负环，因为没有负环的话，对每个点都松弛了，
一定能够有最小值

bool find_negative_loop()
{
	memset(d, 0, sizeof(d));
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
		{
			int u = e[j].u, v = e[j].v, w = e[j].w;
			if(d[u] + w < d[v])
			{
				d[v] = d[u] + w;
				if(i == n-1)
				return true;
			}
		}
	return false;
}