标签：dist idx val int 短路 st

图的最短路：

最短路问题分类：

1.单源最短路，也就是只有一个起点终点

单源最短路又可以分成边权为正与边权为负两类

2.多源最短路，其中有多个起点与终点。

存图方式:

1.以邻接矩阵存储（也就是二维数组：g[i] [j] = k表示i到j有一条长度为k的边），这种方式主要适用于稠密图（边数接近点数的平方的图）

2.以领接表存储（链表），这种方式适合稀疏图。

一、单源最短路（且边权为正）

dijkstra算法（主要处理稠密图问题）

数组： dist[i]：表示第i个点到原点的最短距离 gi：表示点i到j的距离（没有边时值为无穷大） st[i]：记录节点i是否以及被遍历过

主要思路：

基于贪心思想。遍历n次，每次找到当前状态下dist值最小的节点，由这个节点发散出去求得的距离也会是最小的，所以此时还要遍历整张图以更新其它点的最短路，并用st数组标记该点已经遍历过时间复杂度：由于整个遍历了两次整张图，所以复杂度为O(n ^ 2)

代码实现：

#include <bits/stdc++.h>
using namespace std;
const int N = 501;
int n, m;
int g[N][N];
int dist[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] == false && (t == -1 || dist[t] > dist[j])) {
                t = j;
            }//找到当前dist最小的点,由这个点发散出去的点得到的值也一定是最小的 
        }
        st[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;
    else return dist[n];
}
int main() {
    cin.tie();
    cout.tie();
    
    memset(g, 0x3f, sizeof(g));
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);//保证没有自环 
    }
    
    int t = dijkstra();
    cout << t << endl;
    return 0;
}

堆优化：

在dijkstra算法的基础上用小根堆维护了上述每次找最小dist的过程小根堆每次插入数值的时间复杂度为O(logn)，且邻接表以边的形式存储。

总时间复杂度为O(mlogn)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
pair <int, int> PLL;
int n, m;
int h[N], e[N], ne[N], val[N], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c) {
    e[idx] = b;
    val[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
    idx++;
}
int dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    priority_queue <PLL, vector<PLL>, greater<PLL> > heap;
    //pair在不明确声明的情况下以第一个元素比较 
    heap.push({0, 1});
    while(heap.size() != 0) {
        PLL t = heap.top();
        heap.pop();
        int dis = t.first;
        int ver = t.second;
        
        if(st[ver] == true) continue;
        st[ver] = true;
        
        for(int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if(dist[j] > dis + val[i]) {
                dist[j] = dis + val[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);
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    int t = dijkstra();
    printf("%d\n", t);
    return 0;
}

二、单源最短路 (存在负边权)

Bellman-ford算法(唯一可以处理限制最短路边数问题的算法)

结构体：

储存边：起始点，终点，边权值数组：

backup[]：保存上次迭代后的dist数组，防止在本次迭代中循环时，先行更新的dist值会对后续更新的dist值做干扰

dist[i]：表示第i个点到原点的最短距离

主要思路：

循环k次，每次遍历所有的边，看似把所有的边都遍历了一遍，实际只会更新一个节点的dist值，所以外层循环k次刚好表示经过了k条边

时间复杂度： O(nm)

代码实现：

#include <bits/stdc++.h>
using namespace std;
const int N = 501, M = 1e5 + 10;
int n, m, k;
int dist[N], backup[N];
struct Edge {
    int a, b;
    int e;
}edge[M];
int bellman_ford() {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    for(int i = 1; i <= k; i++) {
        memcpy(backup, dist, sizeof(dist)); 
        for(int j = 1; j <= m; j++) {
            int a = edge[j].a, b = edge[j].b, e = edge[j].e;
            dist[b] = min(dist[b], backup[a] + e);
        }//看似遍历了所有的边,其实只有相邻的点被更新了 
    }
    //cout << dist[n] << endl;
    if(dist[n] > 0x3f3f3f3f / 2) return -0x3f3f3f3f;//防止无穷减去一个小边权小于无穷的情况
    else return dist[n]; 
}

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

spfa算法（邻接表存储，无负环情况）

数组： 与dijkstra算法相似

主要思路： spfa算法的代码看似与堆优化的dijkstra算法类似，实则有不同：

Dijkstra算法是基于贪心和DP的思路，一开始先将所有点到原点的距离设置为无穷大，特别的是dis[s]=0,此处的s为原点，它是每次找到离原点最近的点，放入堆中（成为堆顶）并且标记，再以这个点为起点去更新与它相连的点，类似于bfs,而bfs具有短视的特点，它只能看到与它直接相连的点，这也就决定了Dijkstra算法不能处理负权图，假设第一次找到了离原点最近的点为X，再以X为起点去更新与X相连的点，如果存在负边的话，那我找的与X相连的点到X的距离也就不一定是最小了，这就破坏了贪心的思路，算法也就出问题了

SPFA算法：它是要对所有的边去进行一次松弛操作，进行了n-1次更新，先初始化dis数组，起点赋值为0，其余赋值为无穷大，先起点入队列，入了队列的被标记，当队列不为空时循环，队首元素出队，松弛与队首元素相连的边，这些被更新的点如果不在队列中就加入队列，再次队首元素出队，松弛与队首元素相连的边，它是不需要去找离原点最近的点的，所以Dijkstra算法用的是小根堆优化，SPFA直接用的队列

代码实现：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, k;
int e[N], ne[N], h[N], val[N], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c) {
    e[idx] = b;
    val[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
    idx++;
}
int spfa() {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    queue <int> q;
    q.push(1);
    st[1] = true;
    while(q.size() != 0) {
        int 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] + val[i]) {
                dist[j] = dist[t] + val[i];
                if(st[j] == false) {
                    st[j] = true;
                    q.push(j);    
                }
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -0x3f3f3f3f;
    else return dist[n];
}

int main() {
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    int t = spfa();
    if(t == -0x3f3f3f3f) puts("impossible");
    else printf("%d", t);
    return 0;
}

spfa算法判断负环

数组： cnt[i]：记录从原点到i节点最短路的节点数，>n表示一定出现了环，而在最短路过程中出现环一定就是负环 代码实现：

#include <bits/stdc++.h>
using namespace std;
const int N = 2001, M = 1e5 + 10;
int n, m;
int e[M], ne[M], h[N], val[M], idx;
int dist[N];
int cnt[N];
bool st[N];
void add(int a, int b, int c) {
    e[idx] = b;
    ne[idx] = h[a];
    val[idx] = c;
    h[a] = idx;
    idx++;
}
bool spfa() {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 1;
    queue <int> q;
    for(int i = 1; i <= n; i++) q.push(i);//负环不一定在1节点开始 
    while(q.size() != 0) {
        int t = q.front();
        q.pop();
        
        for(int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if(dist[j] > dist[t] + val[i]) {
                dist[j] = dist[t] + val[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] > n) return true;
                q.push(j);
            }
        }
    }
    return false;
}
int main() {
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }
    if(spfa() == false) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}

多源汇最短路

Floyd算法

数组： d[i] [j]：表示从i到j的最短路长度 主要思路： 动态规划

实现代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;

int n, m, q;
int d[N][N];

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]);
}

int main() {
    cin >> n >> m >> q;
    
    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;
    
    for(int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        d[x][y] = min(d[x][y], z);
    }
    floyd();
    while(q--) {
        int x, y;
        cin >> x >> y;
        if(d[x][y] == INF) cout << "impossible" << endl;
        else cout << d[x][y] << endl; 
    }
    return 0;
}

参考：https://blog.csdn.net/luogu_bling/article/details/127231531

标签：dist,idx,val,int,短路,st
From： https://www.cnblogs.com/yjs0914/p/17585009.html

图的最短路