最短路

约 615 个字 157 行代码 预计阅读时间 5 分钟

#图论

Floyed

单元最广路线太复杂了，多源最短路还是可以用的
\(O(N^3)\)

C++

#include <cstring>
#include <iostream>
#define int long long
using namespace std;
int f[105][105];
signed main()
{
    int n, m;
    memset(f, 0x3f3f3f3f, sizeof(f));
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        f[x][y] = f[y][x] = min(f[x][y], z);
    }
    for (int i = 1; i <= n; i++) {
        f[i][i] = 0;
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << f[i][j] << " ";
        }
        cout << endl;
    }
}

Bellman–Ford 算法

可以找到单源最短路径，还能检测负环.
S是源点
利用松弛(relax)操作的最短路
即对于边\((u,v)\)尝试用\((S\rightarrow u \rightarrow v)\)更新长度
\(dis(v)=min(dis(v),dis(u)+w(u,v))\)
SPFA是Bellman–Ford 的一种实现
核心原理是每一轮松弛能到达的边

C++

struct Edge { 
    int u, v, w; 
};
vector<Edge> edge;
bool bellmanford(int s){//s是源点
    memset(d,inf,sizeof(d));//所有点的距离初始化为很大的整数
    dis[s]=0;//自己本身的距离是0;
    bool flag;//判断本轮循环中是否松弛;
    for(int i=1;i<=n;i++){//最多n论,因为每次松弛都会让最短路径的长度加1,如果n轮后仍然可以松弛,说明有负环
        flag=false;
        for(int j=0;j<edge.size();j++){
        int u=edge[j].u,v=edge[j].v,w=edge[j].w;
        if(dis[u]==inf) continue;//还没有被更新的节点不可能是最短路径上的一点
        if(dis[v]>dis[u]+w){
            dis[v]=dis[u]+w;
            flag=true;      
        }
        }
        if(!flag){
            break;//没有边可以松弛了,意味着结束
        }
    }
    return flag;//如果n论后flag还是true,说明有负环

}

算法的复杂程度是O(mn),
显然,可以队列优化,即SPFA,一般最短路还是迪杰斯特拉比较好

SPFA

C++

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 10005;
int n, m, s;
struct edge {
    int u, v, w;
};
vector<edge> e[MAXN];
int dis[MAXN], cnt[MAXN], vis[MAXN];  // cnt最短路经过的边数
queue<int> q;
bool spfa(int n, int s)
{
    for (int i = 1; i <= n; i++) {
        dis[i] = (1ll << 31) - 1;
    }
    dis[s] = 0;
    vis[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (auto ele : e[u]) {
            int v = ele.v, w = ele.w;
            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;
}
signed main()
{
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({u, v, w});
    }
    spfa(n, s);
    for (int i = 1; i <= n; i++) {
        cout << dis[i] << " ";
    }
    return 0;
}

Dijkstra算法

C++

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct edge {
    int v, w;
};
vector<edge> e[MAXN];
struct Polar {
    int dis, u;
    friend bool operator>(const Polar& a, const Polar& b) { return a.dis > b.dis; }
};
int dis[MAXN], vis[MAXN];
priority_queue<Polar, vector<Polar>, greater<Polar>> q;
void dijkstra(int n, int s)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        int u = q.top().u;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto ele : e[u]) {
            int v = ele.v, w = ele.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
}
int main()
{
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
    }
    dijkstra(n, s);
    for (int i = 1; i <= n; i++) {
        cout << dis[i] << " ";
    }
}

一些概念

路径 (Path)

在图论中，路径是顶点的一个序列，其中相邻顶点之间都有边连接。路径可以分为简单路径（顶点不重复）和一般路径（顶点可以重复）。

最短路 (Shortest Path)

最短路径是从图中的一个顶点到另一个顶点的路径，其中路径上的边的总权重最小。最短路径问题通常有不同的变种，取决于图的性质和具体需求。

有向图中的最短路 (Shortest Path in Directed Graph)

有向图中的最短路径问题是寻找从一个起点顶点到终点顶点的路径，其中路径上的边的方向必须被遵循。例如，给定顶点 u 和顶点 v，我们寻找一条从 u 到 v 的路径，使得路径上的边的总权重最小。

### 单源最短路 (Single Source Shortest Path)

单源最短路径问题是从图中的一个起点顶点（源点）出发，找到该顶点到图中所有其他顶点的最短路径。例如，Dijkstra算法和Bellman-Ford算法就是解决单源最短路径问题的经典算法。

无向图中的最短路 (Shortest Path in Undirected Graph)

无向图中的最短路径问题类似于有向图，但不同之处在于，边没有方向。因此，从顶点 uuu 到顶点 vvv 的路径可以沿任意方向行走，寻找路径上的边的总权重最小的路径。

负环

在图论中，负环是一个图中总权重为负数的环。具体来说，负环是指一条闭合路径，这条路径的边权重之和小于零
有负环可以无限减少路径