最短路
有向图中的最短路、无向图中的最短路
单源最短路、每对结点之间的最短路

任意两个结点之间的最短路

Floyd

用来求任意两个结点之间的最短路。
复杂度比较高，但是常数小，容易实现（只有三个 for）。
适用于任何图，不管有向无向，边权正负，但是最短路必须存在（不能有负环）

与坐标结合应用的最短路

Nearest Excluded Points

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;

int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };

void deer()
{
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (auto& [x, y] : a)  cin >> x >> y;      //坐标存在a中

    set<pair<int, int>> st(a.begin(), a.end());     //坐标copy到st中
    map<pair<int, int>, pair<int, int>> ans;    //键坐标对应找的的答案坐标为值
    queue<pair<int, int>> q;
    for (auto [x, y] : a)       //取a中坐标
    {
        for (int i = 0;i < 4;i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (st.count({ nx,ny }))   continue;    //存在则不可用，继续找下一个
            ans[{x, y}] = { nx,ny };    //可用,则push为答案
            q.push({ x,y });    //找到答案后推进去
            break;
        }
    }

    while (!q.empty())
    {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0;i < 4;i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (!st.count({ nx,ny }) || ans.count({ nx,ny }))    continue;
            //排除不是原点或者已记录为答案的点，继续寻找，把原坐标的对应答案找齐
            ans[{nx, ny}] = ans[{x, y}];    //记录已经找过的或原坐标
            q.push({ nx,ny });  //在移动点基础上再寻找
        }
    }

    for (auto [x, y] : a)
    {
        auto it = ans[{x, y}];
        cout << it.first<<" "<<it.second << "\n";
    }
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
//  cin>>t;
    while (t--)
    {
        deer();
    }

    return 0;
}

单源最短路：

DAGDP

DAG：有向无环图
算法思路：
DP依据：对于起始点到终点路径上的每个点都最短，则到达终点的长度一定最短
转移方程(u->v) dis[v]=min(dis[v],dis[v]+w[u][v])
转移顺序：拓扑序
当一个点的入度为0时，则到这个点的所有路径已经找出，即能确定到该点的最小距离，则从这个点往下更新

负权边最短路

Bellman-Ford

Bellman–Ford 算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。

思路：
初始化源点s到各个点的路径 dis[v]=INF,dis[s]=0 (dis[]指当前点到源点距离)
进行n-1次遍历,每次遍历对所有边进行松弛操作,若满足 dis[v]>dis[u]+w(u->v) 则将权值更新
当n-1次遍历结束后,若再进行一次遍历还能得到更短的路径的话，则存在负环回路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int INF=0x3f3f3f3f; //无穷大
struct Edge
{
    int v,w;
};
vector<Edge> e[N];
int dis[N];
int n,m,s,u,v,w;

bool Bellman(int s)
{
    memset(dis,INF,sizeof(dis));
    dis[s]=0;
    bool flag; //标记，用于判断一轮循环中是否有松弛操作
    for(int i=1;i<=n;i++)
    {
        flag=false;
        for(int u=1;u<=n;u++)   //起点j
        {
            if(d[u]==INF)   continue;
            for(auto &[v,w]=edges[u])   //取终点和边权
            {
                if(dis[v]>dis[u]+w)
                {
                    dis[v]=dis[u]+w;
                    flag=true;
                }
            }
        }
        if(!flag) break; //没有可以松弛的边时就停止算法
    }
    return flag; //第n轮flag==true则说明s点可以抵达一个负环
}

int main()
{
    cin>>n>>m>>s;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v>>w;
        e[u].push_back{(v,w)};
    }
    Bellman(s);
}

以 S 点为源点跑 Bellman–Ford 算法时，如果没有给出存在负环的结果，只能说明从 S 点出发不能抵达一个负环，而不能说明图上不存在负环。
判断整个图上是否存在负环: 建立一个超级源点，向图上每个节点连一条权值为 0 的边，然后以超级源点为起点执行 Bellman–Ford 算法。

队列优化:SPFA

Shortest Path Faster Algorithm

只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。
用队列来维护「哪些结点可能会引起松弛操作」，只访问必要的边

SPFA 也可以用于判断 s 点是否能抵达一个负环，只需记录最短路经过了多少条边，当经过了至少 n 条边时，说明 s 点可以抵达一个负环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
struct Edge
{
    int v,w;
};
vector<Edge> e[N];
int dis[N],cnt[N],vis[N];
queue<int> q;

bool spfa(int s)
{
    memset(dis,INF,sizeof(dis));
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(auto &[v,w]=edges[j])
        {
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1; //记录最短路经过的边数
                if(cnt[v]>=n)  return false;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return true;
}