最短路模板

最短路问题中有很多的算法，dijkstra bellman_ford spfa floyd初学真的好难记（更不用说去看算法导论的详细证明了）。y总也总结了很多模板链接，自己再来总结一下加深记忆。另外安利y总算法课，讲的真的很好，我觉得收获很大，而且价格也很良心😂😂。

Dijkstra算法

朴素版dijkstra适合稠密图

思路

集合S为已经确定最短路径的点集。
1. 初始化距离
一号结点的距离为零，其他结点的距离设为无穷大（看具体的题）。
2. 循环n次，每一次将集合S之外距离最短X的点加入到S中去（这里的距离最短指的是距离1号点最近。点X的路径一定最短，基于贪心，严格证明待看）。然后用点X更新X邻接点的距离。

时间复杂度分析

寻找路径最短的点：O(n^2)

加入集合S：O(n)

更新距离：O(m)

所以总的时间复杂度为O(n^2)

具体题目

稠密图用邻接矩阵存。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 510, M = 10010;

int g[N][N], dist[N];
bool visited[N];

int n, m;

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(!visited[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }
        visited[t] = true;
        for(int j = 1; j <= n; j++)
			dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
	scanf("%d%d", &n, &m);
   	
    memset(g, 0x3f, sizeof(g));
    while (m--)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
       	g[x][y] = min(g[x][y], c);
    }
   	cout << dijkstra() << endl;
    return 0;
}

堆优化版dijkstra适合稀疏图

思路

堆优化版的dijkstra是对朴素版dijkstra进行了优化，在朴素版dijkstra中时间复杂度最高的寻找距离最短的点O(n^2)可以使用最小堆优化。
1. 一号点的距离初始化为零，其他点初始化成无穷大。
2. 将一号点放入堆中。
3. 不断循环，直到堆空。每一次循环中执行的操作为：
	弹出堆顶（与朴素版diijkstra找到S外距离最短的点相同，并标记该点的最短路径已经确定）。
	用该点更新临界点的距离，若更新成功就加入到堆中。

时间复杂度分析

寻找路径最短的点：O(n)

加入集合S：O(n)

更新距离：O(mlogn)

具体题目

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

// 稀疏图用邻接表来存
int h[N], e[N], ne[N], idx;
int w[N]; // 用来存权重
int dist[N];
bool st[N]; // 如果为true说明这个点的最短路径已经确定

int n, m;

void add(int x, int y, int c)
{
    w[idx] = c; // 有重边也不要紧，假设1->2有权重为2和3的边，再遍历到点1的时候2号点的距离会更新两次放入堆中
    e[idx] = y; // 这样堆中会有很多冗余的点，但是在弹出的时候还是会弹出最小值2+x（x为之前确定的最短路径），并
    ne[idx] = h[x]; // 标记st为true，所以下一次弹出3+x会continue不会向下执行。
    h[x] = idx++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[0] = 1;
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义一个小根堆
    // 这里heap中为什么要存pair呢，首先小根堆是根据距离来排的，所以有一个变量要是距离，其次在从堆中拿出来的时	  
    // 候要知道知道这个点是哪个点，不然怎么更新邻接点呢？所以第二个变量要存点。
    heap.push({ 0, 1 }); // 这个顺序不能倒，pair排序时是先根据first，再根据second，这里显然要根据距离排序
   	while(heap.size())
    {
        PII k = heap.top(); // 取不在集合S中距离最短的点
        heap.pop();
        int ver = k.second, distance = k.first;
        
        if(st[ver]) continue;
        st[ver] = true;
        
        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i]; // i只是个下标，e中在存的是i这个下标对应的点。
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
               	heap.push({ dist[j], j });
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    
    while (m--)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c);
    }
    
    cout << dijkstra() << endl;
    
    return 0;
}

Bellman_ford算法

Bellman_ford可以解决有负权的图

思路

循环n次，在每一次的循环当中，遍历所有的边 a->b 权重为 w ，dist[b] = min(dist[b], dist[a] + w)。严格证明待看
循环的次数是有实际的意义的，假如循环k次则 dist[x] 代表着从一号点不超过k条边（<=k）的最短距离。

时间复杂度分析

循环n次，每一次遍历m条边，所以时间复杂度为：O(nm)

具体题目

因为这道题在每一次迭代的过程中需要遍历所有的边，所以y总直接用的结构体数组存的。

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int N = 510, M = 10010;

struct Edge
{
    int x, y, c;
}edges[M];
int dist[N], backup[N];

int n, m, k;

int bellman_ford()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    
    for(int i = 0; i < k; i++)
    {
        memcpy(backup, dist, sizeof(dist));
        for(int j = 1; j <= m; j++)
        {
            int x = edges[j].x, y = edges[j].y, c = edges[j].c;
            if(dist[y] > backup[x] + c)
                dist[y] = backup[x] + c;
        }
    }
    if(dist[n] > 0x3f3f3f3f / 2) return -1; // 极端情况 dist[n] = 10000*498;
    else return dist[n];
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
    
    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        //edges[i] = {x, y, c}; c++11
        edges[i].x = x;
        edges[i].y = y;
        edges[i].c = c;
    }
    
    int ret = bellman_ford();
    
    if(ret == -1) puts("impossible");
    else cout << ret << endl;
    
    return 0;
}

spfa算法

思路

spfa算法实际上是对bellman_ford算法的优化。
在bellman_ford当中会将所有的边进行松弛操作，但其实没有必要，其实只需用已经更新过距离的点去更新其他的点就好了。
1. 初始化距离
一号点距离为零，其他点设为无穷大
2. 循环
将一号点加入到队列中;
while(队列不空)
    取点;弹出;更新;

时间复杂度

最好：O(m)

最坏：O(nm)

具体题目

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

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

int n, m;

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

int spfa()
{
    queue<int> q;
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    q.push(1);
    st[1] = true;
    while(q.size())
    {
        int k = q.front();
        q.pop();
        st[k] = false;
        for(int i = h[k]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[k] + w[i])
            {
                dist[j] = dist[k] + w[i];
                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return dist[n];
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);

    while (m--)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c);
    }

    int t = spfa();

    if(t == INF) puts("impossible");
    else cout << t;
    
    return 0;
}

spfa判断负环

思路