最短路

· · 算法·理论

spfa

时间复杂度O(n)-O(nm)

#include <bits/stdc++.h>
using namespace std;
struct poi{
    int v, w;
};
int n, m, s;
queue<int> q;
bool vis[100005];
long long d[100005];
long long cnt[100005];
vector<poi> g[100005];
void spfa(int st)
{
    memset(d, 127, sizeof(d));
    memset(vis, 0, sizeof(vis));
    d[st] = 0;
    vis[st] = 1;
    q.push(st);
    while(!q.empty()){
        int k = q.front();
        q.pop();
        vis[k] = 0;
        for(int i = 0; i < g[k].size(); i++){
            int v = g[k][i].v;
            int w = g[k][i].w;
            if(d[k] + w < d[v]){
                d[v] = d[k] + w;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                    cnt[v]++;
                    if(cnt[k] > n) cout << -1, exit(0);//负环
                }
            }
        }
    }
}
int main()
{
    cin >> n >> m >> s;
    for(int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back((poi){b, c});
    }
    spfa(s);
    cout << d[n];
    return 0;
}

dijkstra

```cpp #include <bits/stdc++.h> using namespace std; struct edge{ int v, w; }; vector<edge> g[10005]; int d[10005], vis[10005]; void dijkstra(int st) { memset(d, 127, sizeof(d)); d[st] = 0;//从起点出发 for(int i = 1; i <= n; i++){ int t = d[0], k; for(int j = 1; j <= n; j++){ if(!vis[j] && d[j] < t){ t = d[j]; k = j; } } for(int j = 0; j < g[k].size(); j++){ int val = g[k][j].v; int wal = g[k][j].w; if(d[val] > d[k] + wal) d[val] = d[k] + wal; } vis[k] = 1; } } int main() { return 0; } ``` $O（nlogn）$**做法**： ```cpp #include <iostream> #include <queue> #include <cstring> #define int long long using namespace std; int n, m, st; struct poi{ int v, w; bool operator < (poi x) const{ return w > x.w; } }; const int N = 2e5 + 5; int d[N], vis[N]; vector<poi> g[N]; priority_queue<poi> q; void dijkstra(int st) { memset(d, 0x3f, sizeof(d)); d[st] = 0; q.push({st, 0}); while(!q.empty()){ int u = q.top().v; q.pop(); if(vis[u]) continue; vis[u] = 1; for(int i = 0; i < g[u].size(); i++){ int v = g[u][i].v, w = g[u][i].w; if(d[u] + w < d[v]){ d[v] = d[u] + w; q.push({v, d[v]}); } } } } signed main() { cin >> n >> m >> st; for(int i = 1; i <= m; i++){ int u, v, w; cin >> u >> v >> w; g[u].push_back((poi){v, w}); } dijkstra(st); for(int i = 1; i <= n; i++) cout << d[i] << " "; return 0; } ``` # $Floyd 
void floyd()
{
    memset(f, 127, sizeof(f));
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            f[i][i] = 0;
            for(int j = 1; j <= n; j++){
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }           
}