声明：

本文仅为作者为了复习而写，并非作为教程使用！

常见的最短路算法：

常见的最短路算法一般有：BFS、DFS、Floyd、Dijkstra、Bellman-Ford、SPFA、Johnson。

常见的存图方式：

1.邻接表 2.链式前向星(习惯)

1..邻接表

优点：1.空间复杂度低，适合存储稀疏图（边数较少的图）。2.插入和删除边的操作效率较高。

缺点：1.历遍所有边时，需要遍历每个顶点的链表，效率较低。2.不适合存储稠密图（边数接近顶点数的平方）。

适合场景：存储边数较少的图，如社交网络、交通网络等。

2..链式前向星

优点：1.效率高，所有数据存储在数组中，访问速度快。2.适合存储稀疏图，同时支持高效的边的插入和遍历。

缺点：1.实现相对复杂，需要维护多个数组。2.对于稠密图，空间浪费可能较大。

适合场景：适合存储边数较多但仍然稀疏的图，如大规模的网络拓扑结构。

总结：

邻接表：适合稀疏图，实现简单，插入和删除边效率高。
链式前向星：适合稀疏图，空间效率高，支持快速遍历和插入边。

最短路基础算法(大多数收集为板子)

1.租用游艇(福建夏令营) 普及-

~~开胃小菜~~

经典的最短路，不过半矩阵的存图方式需要构思一下，类似一个对角矩阵，抽象成上三角矩阵来存图。邻接表时间复杂度O(n²) ，链式前向星(堆优化dijkstra) 时间复杂度O(nlogn)

题目描述

长江游艇俱乐部在长江上设置了 n 个游艇出租站 1,2,⋯,n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金为 r(i,j)（1≤i<j≤n）。试设计一个算法，计算出从游艇出租站 1 到游艇出租站 n 所需的最少租金。
输入格式：第一行中有一个正整数 n，表示有 n 个游艇出租站。接下来的 n−1 行是一个半矩阵 r(i,j)（1≤i<j≤n）。
输出格式：输出计算出的从游艇出租站 1 到游艇出租站 n 所需的最少租金。

示例

输入样例： 3 5 15 7 输出样例：12 解释：第一行的数字 3 表示有 3 个游艇出租站。接下来的两行表示租金信息：第二行的数字 5 和 15 表示从出租站 1 到出租站 2 的租金是 5，从出租站 1 到出租站 3 的租金是 15。第三行的数字 7 表示从出租站 2 到出租站 3 的租金是 7。我们需要找到从出租站 1 到出租站 3 的最少租金。我们可以选择直接从出租站 1 到出租站 3，租金是 15。或者，我们可以选择从出租站 1 到出租站 2，然后从出租站 2 到出租站 3，总租金是 5 + 7 = 12。因此，从出租站 1 到出租站 3 的最少租金是 12.

--实现方式

邻接矩阵实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <map>
#include <cstring>
#include <cmath>
#include <unordered_set>
#include <set>
#include <utility>
#include <climits>

#define int long long
#define PII pair<int, int>
#define inf 0x3f3f3f
#define all(v) (v.begin() , v.end())

using namespace std;
const int N = 220;

int n;
int dist[N] , g[N][N];
bool st[N];

int dijkstra()
{
    memset(dist , 0x3f , sizeof dist);

    dist[1] = 0;
    
    for (int i = 1 ; i <= n ; i ++ ) 
    {
        int t = -1;
        for (int j = 1 ; j <= n ; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        st[t] = true;

        for (int j = 1 ; j <= n ; j ++ )
            dist[j] = min(dist[j] , dist[t] + g[t][j]);
    }

    return dist[n];
}

void solve() 
{
    cin >> n;

    memset(g , 0x3f , sizeof g);

    for (int i = 1 ; i < n ; i ++ ) 
    {
        for (int j = i + 1 ; j <= n ; j ++ ) 
        {
            cin >> g[i][j];
        }
    }

    cout << dijkstra() << endl;

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    solve();
    return 0;
}

链式前向星实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <map>
#include <cstring>
#include <cmath>
#include <unordered_set>
#include <set>
#include <utility>
#include <climits>

// #define int long long
#define PII pair<int, int> 
#define inf 0x3f
#define all(v) v.begin() , v.end()

using namespace std;
const int N = 1e6  + 10;

int e[N] , w[N] , ne[N] , dist[N] , h[N] , idx;
int n;
bool st[N];

void add(int a , int b , int c)
{
    e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx ++;
}

void dijkstra()
{
    memset(dist , 0x3f , sizeof dist);
    memset(st , false , sizeof st);
    dist[1] = 0;

    priority_queue<PII , vector<PII> , greater<PII>> heap;
    heap.push({0 , 1});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int distance = t.first , index = t.second;

        if (st[index]) continue;
        st[index] = true;

        for (int i = h[index] ; i != -1 ; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j] , j});
            }
        }
    }
}

void solve()  
{   
    memset(h , -1 , sizeof h);
    cin >> n;
    for (int i = 1 ; i < n ; i ++ ) 
    {
        for (int j = i + 1 ; j <= n ; j ++ )
        {
            int distance;
            cin >> distance;
            add(i , j , distance);
        }
    }    

    dijkstra();

    cout << dist[n] << endl;
}

signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    solve();
    return 0;
}

dp解法：

下次再补>-..-<

2.单源最短路模板(dijkstra堆优化模板) 提高-

dijkstra堆优化版时间复杂O(nlogn) , 可过1e5 以上的数据。同样可使用朴素版dijkstra和spfa 时间复杂度O(n²)。1e5数据会被卡。

题目描述

给定一个 n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。数据保证你能从 s 出发到任意点。
输入格式：第一行为三个正整数 n,m,s。第二行起 m 行，每行三个非负整数 u i ,v i ,w i ，表示从 u i 到 v i 有一条权值为 w i 的有向边。
输出格式：输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。

示例

输入：
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出：
0 2 4 3

代码

const int N = 1e6 + 10;
int e[N] , ne[N] , h[N] , w[N] , dist[N] , idx;

void add(int a , int b , int c)
{
    e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx ++;
}
bool st[N];

void dijkstra(int s)
{
    memset(dist , 0x3f , sizeof dist);
    memset(st , false , sizeof st);

    dist[s] = 0;
    priority_queue<PII , vector<PII> , greater<PII> > heap;
    heap.push({0 , s});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int distance = t.first , index = t.second;

        if (st[index]) continue;
        st[index] = true;

        for (int i = h[index] ; ~i ; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j] , j});
            }
        }
    }
}

void solve()
{
    memset(h , -1 , sizeof h);
    int n , m , s;
    cin >> n >> m >> s;

    for (int i = 1 ; i <= m ; i ++ )
    {
        int a , b , c;
        cin >> a >> b >> c;
        add(a , b , c);
    }

    dijkstra(s);
    
    for (int i = 1 ; i <= n ; i ++ )
        cout << dist[i] << " ";
}

3.负环(spfa) 提高-

记录每次更新最短路劲的个数，如果更新大于等于n 则说明出现了负环。大于n则说明有至少一个点使用了多次，使用多次只能是每次更新最短路径的适合经过他都能更小，那么只能是负环。使用spfa优化计数时间复杂度 O(n²)

题目描述

给定一个 n 个点的有向图，请求出图中是否存在从顶点 1 出发能到达的负环。负环的定义是：一条边权之和为负数的回路
输入格式：本题单测试点有多组测试数据。输入的第一行是一个整数 T，表示测试数据的组数。对于每组数据的格式如下：
第一行有两个整数，分别表示图的点数 n 和接下来给出边信息的条数 m。接下来 m 行，每行三个整数 u,v,w。若 w≥0，则表示存在一条从 u 至 v 边权为 w 的边，还存在一条从 v 至 u 边权为 w 的边。若 w<0，则只表示存在一条从 u 至 v 边权为 w 的边。
输出格式：对于每组数据，输出一行一个字符串，若所求负环存在，则输出 YES，否则输出 NO

示例

输入：
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8
输出：
NO
YES

代码

const int N = 1e4 + 10 , M = 4 * N;
int e[M] , ne[M] , h[N] , w[M] , dist[M] , idx;
bool st[M];
int cnt[M];
int n , m;

void add(int a , int b , int c)
{
    e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx ++ ;
}

bool spfa()
{
    memset(dist , 0x3f , sizeof dist);
    memset(st , false , sizeof st);
    memset(cnt , 0 , sizeof cnt);

    queue<int> q;
    q.push(1);
    st[1] = true;
    dist[1] = 0;

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = false;

        for(int i = h[t] ; i != -1 ; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;

                if (cnt[j] >= n) return true;
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

void solve()
{
    int t;
    cin >> t;
    while (t -- )
    {
        memset(h , -1 , sizeof h);
        cin >> n >> m;
        for (int i = 1 ; i <= m ; i ++ )
        {
            int a , b , c;
            cin >> a >> b >> c;
            add(a , b , c);
            if (c >= 0) add(b , a , c);
        }

        if (spfa()) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

4.最短路计数提高/普及+

类spfa做法同时带一点dp思想。当前跟新的最短路径是由上一个位置为终点转移而来的。只需要依次更新即可。放在这个是为了给以后有找最短路的个数留一个板子。时间复杂度O(n + m)

题目描述

给出一个 N 个顶点 M 条边的无向无权图，顶点编号为 1∼N。问从顶点 1 开始，到其他每个点的最短路有几条。
输入格式：第一行包含 2 个正整数 N,M，为图的顶点数与边数。接下来 M 行，每行 2 个正整数 x,y，表示有一条连接顶点 x 和顶点 y 的边，请注意可能有自环与重边。
输出格式：共 N 行，每行一个非负整数，第 i 行输出从顶点 1 到顶点 i 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 ans mod 100003 后的结果即可。如果无法到达顶点 i 则输出 0。

示例

输入：
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5
输出：
1
1
1
2
4

代码

const int mod = 1e5 + 3 , N = 1e6 + 10 , M = 4 * N;
int e[M] , ne[M] , h[N] , idx;
int cnt[M] , dist[M]; 
int n , m;

void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
}

void bfs()
{
    memset(dist , -1 , sizeof dist);
    queue<int> q;

    dist[1] = 0 , cnt[1] = 1;
    q.push(1);

    while (q.size())
    {
        int index = q.front();
        q.pop();

        for (int i = h[index] ; ~i ; i = ne[i])
        {
            int j = e[i];

            if (dist[j] == -1)
            {
                dist[j] = dist[index] + 1;
                cnt[j] = cnt[index];
                q.push(j);
            }
            else if (dist[j] == dist[index] + 1)
            {
                cnt[j] += cnt[index];
                cnt[j] %= mod;
            }
            
        }
    }

}

void solve()
{
    memset(h , -1 , sizeof h);
    cin >> n >> m;
    for (int i = 1 ; i <= m ; i ++ )
    {
        int a , b;
        cin >> a >> b;
        add(a , b) , add(b , a);
    }

    bfs();

    for (int i = 1 ; i <= n ; i ++ ) cout << cnt[i] << endl;
}