一、基础

1、最短路径问题的形式：

单源最短路径：希望找到从源节点s到每个结点的最短路径；

单目的地最短路径：希望找到从每个结点到给定目的地的最短路径，只需将图的每条边方向翻转过来，就可以转化成单源最短路径

单结点对最短路径：希望找到结点u到结点v的最短路径

所有结点对最短路径：对于每对结点u、v，找到从结点u到结点v的最短路径

最长路径：把边权取反，再跑最短路（无环）

2、最短路径算法通常依赖一个重要性质，最优子结构：两个结点之间的一条最短路径包含着其他的最短路径。也就是说，最短路径的子路径也是最短路径。

3、对于权重可能为负值的边权，图中可能存在权重为负值的环路，但是对于有负环的图是没有最短路径的（只需要走一遍负环就可以得到更小的最短路径）

4、由于负环无最短路径、正环和权重为0的环可以删除，我们可以假定找到的最短路径中没有环路，即他们都是简单路径，由于图中任意无环路径最多包含个不同的结点，条边，因此我们可以将注意力集中到只包含 条边的最短路径上

5、最短路径的表示：为了记录计算得到的最短路径上的结点，对于每个结点v我们可以维持其前驱节点pre，将从结点v开始的前驱节点链反转过来，就是s到v的最短路径

6、最短路径树是一棵有根节点的树，该树包括了从源节点s到每个可以从s到达的结点的一条最短路径

7、最短路径不是唯一的，最短路径树也不一定是唯一的

8、松弛操作：对于每个结点，我们可以维持其一个属性dis，用来记录从源节点s到结点v的最短路径权重的上界，我们称dis为s到v的最短路径估计

对属性dis需要初始化为，源节点的dis初始化为0

对一条边(u,v)的松弛过程为：首先测试是否可以对从s到v的最短路径进行改善，如果可以改善，就进行更新。测试的方法是：将从结点s到结点u之间的最短路径加上u到v的权重与当前s到v的最短路径进行比较，如果前者更小，则进行更新

松弛步骤可以降低最短路径的估计值dis并更新v的前驱属性pre

二、Bellman-Ford算法

该算法通过对边进行次松弛操作来渐进的降低从最短路径估计dis，直到估计值与实际最短路径相同为止

struct edge //边
{
	int u, v;
	int cost;
}edge[maxn];
int dis[maxn];		
//跑完Bellaman_Ford后，dis数组是从源点s到各点的最短路径
int n, m, s;
int Bellman_Ford()
{
	for (int i = 1; i <= n; ++i) //初始化
		dis[i] = (i == s ? 0 : inf);
	for (int i = 1; i <= n - 1; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			if (dis[edge[j].v] > dis[edge[j].u] + edge[j].cost)
			{
				dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
			}
		}
	}
	int flag = 1; //判断是否含有负权回路
	for (int i = 1; i <= m; ++i)
	{
		if (dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)
		{
			flag = 0;
			break;
		}
	}
	return flag;
}

for (int i = 1; i <= m; i++)
{
	cin >> edge[i].u >> edge[i].v >> edge[i].cost;
}

Bellman-Ford算法可以应用于负权值，但是由于复杂度过高，有两种方法进行优化：

（1）、对于有向无环图可以进行拓扑排序，根据结点的拓扑排序次序来对带权重的有向无环图进行边的松弛操作。原理：通过拓扑排序可以确定结点之间的线性次序，如果有向无环图包含从u到v的一条路径，则u在次序中位于v前，我们只需要按照拓扑排序的次序对结点进行一次处理即可

该方法运行时间为线性级别，但是只能用于有向无环图

（2）、Bellman-Ford算法在每次松弛时，遍历了所有的边，但每次遍历未必会真的更新最短距离。如果某一轮迭代中松弛操作未执行，说明此次迭代所有的边都没有被松弛，因此可以证明：至此后，边集中所有的边都不需要再被松弛，从而可以提前结束迭代过程。

优化方法：用队列来记录松弛操作被成功执行的结点，如果松弛成功就放入队列继续操作

三、SPFA算法（Bellman-Ford的队列优化）

该算法由于是由Bellman-Ford在特殊情况优化得来，故在最坏情况与Bellman-Ford相同

int n, m, s;
int dis[maxn], vis[maxn], in[maxn];
struct node
{
	int v;
	int weight;
};
vector<node>g[maxn];
int SPFA()
{
	memset(dis, 0x3f, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	memset(in, 0, sizeof(in));
	int q;
	queue<int>Q;
	vis[s] = 1;
	dis[s] = 0;
	Q.push(s);
	while (!Q.empty())
	{
		q = Q.front();
		Q.pop();
		vis[q] = 0;
		for (int i = 0; i < g[q].size(); i++)
		{
			if (dis[q] + g[q][i].weight < dis[g[q][i].v])
			{
				dis[g[q][i].v] = dis[q] + g[q][i].weight;
				if (!vis[g[q][i].v])
				{
					Q.push(g[q][i].v);
					vis[g[q][i].v] = 1;
					if (++in[g[q][i].v] > n)        //超过n次经过一个边必为负环
						return 0;
				}
			}
		}
	}
	return 1;
}
void solve()
{
	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({ v,w });
	}
	if (SPFA())
	{
		for (int i = 1; i <= n; i++)
			cout << dis[i] << " \n"[i == n];
	}
	else
		cout << "存在负环";
}

四、Dijkstra算法

Dijkstra算法的关键在维护一组结点结合S，从源节点s到该集合S的每个节点之间的最短路径已经找到。算法不断从不在集合S中的其他结点中选择最短路径估计最小（优先队列维护）的结点u，并加入到集合S（路径由估计值变为确定值），然后对从u出发的边进行松弛

找到最短路径估计最小的原因：目前离u结点最近的是v结点，由于这个图所有的边都是正数，那么肯定不可能再经过第三个结点，使得u结点到v结点的路程更短

也正是由于上点原因，Dijkstra不可以计算带有负边权的图的最短路径

朴素的dijkstra，时间复杂度O(n^2)，在稠密图时略优于优先队列算法

void dijkstra()
{
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++)
	{
		dis[i] = g[s][i];
	}
	vis[s] = 1;
	for (int i = 1; i <= n; i++)
	{
		int minj = 0;
		for (int j = 1; j <= n; j++)
		{
			if (!vis[j] && (dis[j] < dis[minj] || minj == 0))
				minj = j;
		}
		vis[minj] = 1;
		for (int j = 1; j <= n; j++)
		{
			if (dis[j] > g[minj][j] + dis[minj])
				dis[j] = g[minj][j] + dis[minj];
		}
	}
}

优先队列优化，时间复杂度O(mlogn)，在稀疏图中更优

typedef pair<int, int> pai;
priority_queue<pai, vector<pai>, greater<pai> >q;
vector<pai>g[maxn];        //first边权，second点
int dis[maxn], vis[maxn];    //dis数组跑完之后是从s到各结点的最短路径
int u, v, w, n, m, k;
void dijstra(int s)    //start
{
	int i;
	memset(vis, 0, sizeof(vis));
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	q.push({ dis[s], s });
	while (!q.empty())
	{
		pai e = q.top();
		q.pop();
		int v = e.second;
		if (vis[v])
			continue;
		vis[v] = 1;
		for (i = 0; i < g[v].size(); i++)
		{
			pai e = g[v][i];
			if (dis[e.second] > dis[v] + e.first)
			{
				dis[e.second] = dis[v] + e.first;
				q.push({ dis[e.second], e.second });
			}
		}
	}
}

五、 延申

1、记录路径

使用pre数组记录该下标对应点的前驱

if (dis[edge[j].v] > dis[edge[j].u] + edge[j].cost)
{
	dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
	pre[edge[j].v] = edge[j].u;        //在松弛操作成功的时候记录
}

vector<int>ans;
int j = n;        //从1到n的路径，从n开始往前找
ans.push_back(n);
while (j != 1)        //直到找到1结束
{
	ans.push_back(pre[j]);
	j = pre[j];
}
reverse(ans.begin(), ans.end());
for (auto e : ans)
{
	cout << e << ' ';
}

2、路径较大时，如果dis数组需要开longlong那么inf也要开成INF = 0x3f3f3f3f3f3f3f3f