-1.最短路径
-1.1 Bellman-Ford
Bellman-Ford 是一种最基础的求解单源最短路径的算法，其整体思想是暴力，但是用途十分广泛。
具体实现中，该算法将 \(m\) 条边松弛 \(n - 1\) 次，其中松弛是指对于一条边 \((x, y)\)，如果 \(dis_x + w_{x, y} < dis_y\)，那么将 \(dis_y\) 的值修改为 \(dis_x + w{x, y}\)，意思是如果当前从源点到 \(x\) 的最短路径加上 \((x, y)\) 的边权小于从源点到 \(y\) 的最短路径，那么就找到了一条比原来终点为 \(y\) 的最短路径更短的路径，那么更新。
正确性证明：在一个有 \(n\) 个点的图中，任意两点的最短路至多经过 \(n - 1\) 条边，故至多只需松弛 \(n - 1\) 次。详细证明这里不再阐述。
同时，Bellman-Ford 算法还可以处理有负权边的图的最短路，并且可以判断负环。
但是此算法由于其时间复杂度过高，为 \(\Theta(nm)\)，所以选手一般不使用 Bellman-Ford，而是使用其队列优化版本 SPFA，后文将会详细阐述。
核心代码：
for(int i = 1; i < n; i++)//枚举n - 1轮
for(int j = 1; j <= m; j++)//枚举每一条边
{
int x = e[j].x, y = e[j].y, w = e[j].w;
if(dis[x] + w < dis[y])//松弛操作
dis[y] = dis[x] + w;
}
-1.2 Dijkstra
Dijkstra 是一种基于贪心的一种单源最短路径算法，其整体思想是蓝白点。
在算法实现中， 首先将起点标记为蓝点（求出最短路径的点，反之则白点），然后循环 \(n - 1\)，对于每一次循环，找出当前所有点中距离源点的最短路最小且是白点的点 \(x\)，然后枚举点 \(x\) 的每一个邻接点 \(y\)，进行松弛操作，如果 \(dis_x + w_{x, y} < dis_y\)，那么 \(dis_y\) 更新为 \(dis_x + w{x, y}\)，并且标为蓝点。
关于正确性，此处引用@Alex_Wei 在初级图论中的正确性证明。
归纳假设已经松弛过的节点 \(p_1, p_2, ..., p_{k - 1}\) 在扩展时均取到了其最短路。\(p_k\) 为没有被扩展的 \(dis\) 最小的节点。
\(p_k\) 的最短路一定由 \(p_i(1 \le i < k)\) 的最短路扩展而来，不可能出现 \(dis_{p_i}+w_{p_i,p_k+1}+w_{p_k + 1, p_k} < dis_{p_j} + w_{p_j, p_k}(1 \le i,j < k)\) 的情况。否则由于边权非负，\(w_{p_k + 1, p_k} \le 0\)，所以 \(dis_{p_i} + w_{p_i, p_k + 1} < dis_{p_j} + w_{p_j, p_k}\)，即当前 \(dis_{p_k + 1} < dis_{p_k}\)，与 \(dis_{p_k}\)
的最小性矛盾。
初始令源点 \(s\) 的 \(dis_s\) 为 \(0\) ，假设成立，因此算法正确。
此时该算法的时间复杂度为 \(\Theta(n^2)\)，显然是很慢的，在稀疏图中，还不如可以处理负权边的 Bellman-Ford，所以我们需要优化。
在寻找距离源点的最短路最小的白点时，一个一个找显然很慢，而这里我们可以使用小根堆优化。松弛的时候，只要条件成立，就将这个点压入堆中，然后将这些点一个一个取出对它的邻接点进行松弛。
这里的大根堆可以使用 STL 中的 priority_queue （优先队列）来实现。由于我们需要存储边权和终点，所以优先队列就需要存储 \(2\) 个变量。这里这里介绍 \(2\) 种方法。
\(1\). 重载运算符。定义结构体类型的优先队列，然后重载 <。
代码：
struct Node
{
int x, w;
bool operator < (const Node &b)const//重载运算符
{
return w > b.w;
}
};
priority_queue<Node> pq;
\(2\). pair。定义一个 pair<int, int>类型的优先队列，按照第一个值从大到小排序。
代码：
priority_queue< pair<int, int> > pq;//定义一个pair<int, int>类型的优先队列。
pq.push(make_pair(-dis[y], y));//插入一条边，边权为dis[i]，终点为y，由于默认从大到小排序，所以边权要取负
int x = pq.top().second;//取出一个点
相对来说 pair 要好写一些，这里更加推荐 pair。
此时的时间复杂度降为 \(\Theta(m \log m)\)，十分优秀。
模板题P4779 【模板】单源最短路径（标准版）代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, m, s, dis[N];
bool vis[N];
struct node
{
int y, w;
};
vector<node> e[N];
void dijkstra(int s)
{
for(int i = 1; i <= n; i++)//将dis赋为极大值
dis[i] = INT_MAX;
priority_queue< pair<int, int> > pq;
pq.push(make_pair(0, s));//将源点入队
dis[s] = 0;//源点到源点的距离为0
while(!pq.empty())
{
int x = pq.top().second;
pq.pop();
if(vis[x])//如果是蓝点，那么跳过
continue;
vis[x] = true;//标记为蓝点
int len = e[x].size();
for(int i = 0; i < len; i++)
{
int y = e[x][i].y, w = e[x][i].w;
if(dis[x] + w < dis[y])//松弛操作
{
dis[y] = dis[x] + w;
pq.push(make_pair(-dis[y], y));//入队
}
}
}
return;
}
signed main()
{
cin >> n >> m >> s;
for(int i = 1; i <= m; i++)
{
int x, y, w;
cin >> x >> y >> w;
e[x].push_back({y, w});//建边
}
dijkstra(s);
for(int i = 1; i <= n; i++)
cout << dis[i] << " ";
return 0;
}