图论-最短路

 一、不存在负权边-dijkstra算法

dijkstra算法适用于这样一类问题：

从起点 start 到所有其他节点的最短路径。

其实求解最短路径最暴力的方法就是使用bfs广搜一下，但是要一次求得所有点的最短距离我们不可能循环n次，这样复杂度太高，因此dijlstra算法应运而生，算法流程如下：

（待补充）

对于：

稠密图一般使用邻接矩阵+朴素dji

稀疏图使用邻接表+堆优化dji

1.1 朴素djikstra算法

算法模板：

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 510;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra(){
    memset(st,0,sizeof(st));
    memset(dist,0x3f,sizeof(dist));
    
    dist[1] = 0;
    //对于每个点都要遍历所有点，也即是穷举
    for(int i = 0;i < n; i++){
        int t = -1;//临时存储第i次处理的点
        //一、遍历所有点，在所有没有访问过的点中找到距离最近的点
        for(int j = 1; j<= n;j++)
            if(!st[j] && (t == -1 || dist[t] > dist[j])){
                t = j;
            }
            
        //
        st[t] = true;
        //二、用1-t的路径长度 + t - j的边长度来更新dist[j];
        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];

}

1.2 优先级队列优化的djikstra

首先我们分析，如果是稀疏图，什么导致的朴素版djikstra复杂度高，首先我们用的是邻接表来存图，那么就要用bfs相应的方法进行遍历，那么我们需要先while处理点再内层处理边，如果不优化，复杂度依旧是o(mn)

这是因为我们将所有的顶点都遍历了，用于寻找最小距离点，如果我们使用堆来优化（而不是一般bfs中的普通队列），每次使用优先级队列来存放顶点，因为理想情况下优先级队列中最多装 n 个节点，对优先级队列的操作次数和 m 成正比，所以整体的时间复杂度就是 O(mlogn)。

红字解释：

因为在修改其它顶点最短距离的过程中，堆优化版本并没有遍历所有的顶点，而是遍历所有与当前选取的最小顶点有关的边 ，从一小部分顶点出发就能到达所有顶点，因此没有必要遍历所有顶点

优先级队列解释： 

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

pair中 第一个整数可以表示从源点到该顶点的距离，第二个整数表示顶点的编号。

vector<pair<int, int>>指定了底层容器类型。

greater<>：默认小顶堆，less<>:大顶堆排序

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
//只存一个点，因为另一个点是邻接表的表头
struct Edge {
    int to, weight;
};

vector<Edge> adj[N];
int dist[N];
bool visited[N];

void dijkstra(int source) {
    memset(dist, 0x3f, sizeof(dist));
    memset(visited, 0, sizeof(visited));
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    dist[source] = 0;
    pq.push({0, source});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        for (auto &e : adj[u]) {
            int v = e.to;
            int w = e.weight;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        adj[x].push_back({y, z});
    }

    dijkstra(1); // 假设你想要从节点 1 找到到其他所有节点的最短路径

    if (dist[n] == INF) cout << "-1\n"; // 检查是否存在从1到n的路径
    else cout << dist[n] << "\n";

    return 0;
}

二、存在负权值 -bellma-ford算法

1.朴素Bellman-Ford算法

 三角不等式：

对于所有点都有：

dist[b] <= dist[a] + w

 松弛操作： 

dist[b] = min(dist[b], dist[a] + w)

 注意：如果一个图中存在负权回路，那么可能不存在最短路

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

using namespace std;
const int N = 510;
const int M = 10010;
int n,m,k;
int dist[N],backup[N];
// 边，a表示出点，b表示入点，w表示边的权重
struct edge{
    int from;
    int to;
    int weight;
}edges[M];


void bellman_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1] =0;
// 如果第n次迭代仍然会松弛三角不等式（存在更新），就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for(int i = 0;i < k;i++){
// 备份，防止读后写
        memcpy(backup,dist,sizeof(dist));
        for(int j = 0;j < m; j++){
            int from = edges[j].from;
            int to  = edges[j].to;
            int weight = edges[j].weight;
            dist[to] = min(dist[to],backup[from] + weight);
        }
    }

}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 0;i < m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edges[i] = {a,b,c};
    }
    bellman_ford();
    if(dist[n] > 0x3f3f3f3f/2){
        puts("impossible");
    }else{
        printf("%d\n",dist[n]);
    }
    
    return 0;
}

除了可以用邻接矩阵和邻接表外，还可用三元组存储图
允许存在负权边，而Dijkstra算法不允许
外循环次数决定最小路径的最大边数
若第n次迭代有修改，根据容斥原理知道，一定存在负权环（整个环的权重和为负数）
实际应用：换乘不超过k次的最短路径（限制路径的边数）
backup用于保存上次迭代的结果，避免“写后读”。Dijkstra算法不存在这种情况
由于存在负权回路（注意不是负权边），因此负权回路有可能把自定义的无穷大0x7f7f7f7f变小，由于最多修改10000×10000=108，10000×10000=108，而0x7f7f7f7f>2×108>2×108，故0x7f7f7f7f / 2依旧是“无穷大”，故可用dist[n] > 0x7f7f7f7f / 2判断是否是无穷大
时间复杂度为O(mn)

2.普通队列优化的bellman-ford算法

#include<cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
//只存一个点，因为另一个点是邻接表的表头
struct Edge {
    int to, weight;
};

vector<Edge> adj[N];
int dist[N];
bool used[N];
int n, m,k;

void spfa(int source) {
    memset(dist, 0x3f, sizeof(dist));
    dist[source] = 0;
    queue<int> pq;
    pq.push(source);
    used[source] = true;
    while (!pq.empty()) {
        int u = pq.front();pq.pop();
        used[u] = false;
        for (auto &e : adj[u]) {
            int v = e.to;
            int w = e.weight;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if(!used[v]){
                    pq.push(v);
                    used[v] = true;
                }
                
            }
        }
    }
}

int main() {

    cin >> n >> m ;

    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        adj[x].push_back({y, z});
    }

    spfa(1);
    if(dist[n] > 0x3f3f3f3f/2){
        puts("impossible");
    }else{
        printf("%d\n",dist[n]);
    }

    return 0;
}

时间复杂度：

最好：o(m) 

最差：o（mn）

spfa相较于djikstra,如果题目中不进行针对性限制，一般是会比djikstra更快的

spfa求负环数量：

#include<cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
//只存一个点，因为另一个点是邻接表的表头
struct Edge {
    int to, weight;
};

vector<Edge> adj[N];
int dist[N],cnt[N];
bool used[N];
int n, m,k;
bool iscir = false;

void spfa(int source) {
    // memset(dist, 0x3f, sizeof(dist));
    queue<int> pq;
    for(int i =1;i <= n;i++){
        // dist[i] = 0;
        pq.push(i);
        used[i] = true;
    }

    
    while (!pq.empty()) {
        int u = pq.front();pq.pop();
        used[u] = false;
        for (auto &e : adj[u]) {
            int v = e.to;
            int w = e.weight;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                //判断是否存在负权值
                cnt[v] = cnt[u] + 1;
                if(cnt[v] >= n) {
                    iscir = true;
                    return;
                }
                if(!used[v]){
                    pq.push(v);
                    used[v] = true;
                }
                
            }
        }
    }
}

int main() {

    cin >> n >> m ;

    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        adj[x].push_back({y, z});
    }

    spfa(1);
    if(iscir){
        printf("Yes");
    }else{
        printf("No");
    }

    return 0;
}

三、Floyd算法

const int INF = 1E9;
// 初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

最短距离需要把d[i][i] = 0;
时间复杂度为O(n3)