最短路

Skyzhou666 · 2022-06-09 17:29:28 · 算法·理论

SPFA

#include <iostream>
#include <vector>
#include <queue>
#define MAX 2147483647
using namespace std;

struct Node
{
    int v, dis;
};

vector <Node> a[10001];

int n, m, s, d[10001];
bool vis[10001];

void SPFA()
{
    queue <int> q;
    d[s] = 0;
    vis[s] = true;
    q.push(s);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        //cout << u << endl;
        vis[u] = false;
        for(int x = 0; x < a[u].size(); x++)
        {
            int v = a[u][x].v;
            //cout << "v: " << v << endl;
            if(d[v] > d[u] + a[u][x].dis)
            {
                d[v] = d[u] + a[u][x].dis;
                if(!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m >> s;
    for(int x = 1; x <= n; x++) d[x] = MAX;
    for(int x = 0; x < m; x++)
    {
        int u;
        Node tmp;
        cin >> u >> tmp.v >> tmp.dis;
        a[u].push_back(tmp);
    }
    SPFA();
    for(int x = 1; x <= n; x++) cout << d[x] << " ";
    cout << endl;
    return 0;
}

SPFA（判负环）

#include <bits/stdc++.h>
#define INF 0x7fffffff
#define MAXN 200010
#define LL long long
using namespace std;

struct node
{
    int v, w;
};

int n, m, d[MAXN], cnt[MAXN];
vector <node> g[MAXN];
bool vis[MAXN], findN;

void SPFA(int st)
{
    findN = false;
    for(int x = 0; x < n; x++) d[x] = INF;
    queue <int> q;
    q.push(st);
    d[st] = 0;
    vis[st] = true;
    cnt[st]++;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        vis[u] = false;
        for(int x = 0; x < g[u].size(); x++)
        {
            int v = g[u][x].v, w = g[u][x].w;
            if(d[u] != INF && d[u] + w < d[v])
            {
                d[v] = d[u] + w;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v] = true;
                    cnt[v]++;
                    if(cnt[v] > n)
                    {
                        findN = true;
                        return;
                    }
                }
            }
        }
    }
}

int main()
{
    int st;
    cin >> n >> m >> st;
    for(int x = 1; x <= m; x++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back((node){v, w});
    }
    SPFA(st);
    if(findN)
    {
        cout << "NEGATIVE CYCLE" << endl;
        exit(0);
    }
    for(int x = 0; x < n; x++)
    {
        if(d[x] == INF) cout << "INF" << endl;
        else cout << d[x] << endl;
    }
    return 0;
}

SPFA（链式前向星）

#include <iostream>
#include <cstring>
#include <queue>
#define INF 0x7fffffff
#define MAXN 1000001
using namespace std;

struct Edge
{
    int to, next, w;
} e[MAXN];

int n, m, head[MAXN], cnt, d[MAXN];

void addEdge(int u, int v, int w)
{
    e[cnt].to = v;
    e[cnt].next = head[u];
    e[cnt].w = w;
    head[u] = cnt++;
}

void run(int i)
{
    d[i] = 0;
    queue <int> q;
    q.push(i);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int x = head[u]; x >= 0; x = e[x].next)
        {
            int v = e[x].to, w = e[x].w;
            if(d[u] + w < d[v])
            {
                d[v] = d[u] + w;
                q.push(v);
            }
        }
    }
}

int main()
{
    int s;
    memset(head, -1 ,sizeof(head));
    cin >> n >> m >> s;
    for(int x = 1; x <= n; x++) d[x] = INF;
    for(int x = 0; x < m; x++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        //addEdge(v, u);
    }
    run(s);
    for(int x = 1; x <= n; x++) cout << d[x] << " ";
    cout << endl;
    return 0;
}

Dijkstra（基础）

#include <iostream>
#include <vector>
#define MAX 2147483647
using namespace std;

struct Node
{
    int v, dis;
};

vector <Node> a[100001];
int n, m, s, d[100001];
bool vis[100001];

void Dijkstra()
{
    for(int x = 1; x <= n; x++) d[x] = MAX;
    d[s] = 0;
    for(int x = 1; x <= n; x++)
    {
        int minn = -1, min = MAX;
        for(int y = 1; y <= n; y++)
        {
            if(vis[y] == false && d[y] < min)
            {
                min = d[y];
                minn = y;
            }
        }
        //cout << minn << endl;
        if(minn == -1) return;
        vis[minn] = true;
        for(int y = 0; y < a[minn].size(); y++)
        {
            int v = a[minn][y].v;
            //cout << v << endl;
            if(vis[v] == false && d[minn] + a[minn][y].dis < d[v])
                d[v] = d[minn] + a[minn][y].dis;
        }
    }
}

int main()
{
    cin >> n >> m >> s;
    for(int x = 0; x < m; x++)
    {
        Node tmp;
        int u;
        cin >> u >> tmp.v >> tmp.dis;
        a[u].push_back(tmp);
    }
    Dijkstra();
    for(int x = 1; x <= n; x++) cout << d[x] << " ";
    cout << endl;
    return 0;
}

Dijkstra（小根堆优化）

#include <iostream>
#include <vector>
#include <queue>
#define MAX 2147483647
using namespace std;

struct Node
{
    int v, dis;
};

struct pri
{
    int ans, id;
    bool operator < (const pri &x) const{return x.ans < ans;}
};

priority_queue <pri> q;
vector <Node> a[100001];
int n, m, s, d[100001];
bool vis[100001];

void Dijkstra()
{
    for(int x = 1; x <= n; x++) d[x] = MAX;
    d[s] = 0;

    q.push((pri){0, s});
    while(!q.empty())
    {
        pri tmp = q.top();
        q.pop();
        int minn = tmp.id;
        if(!vis[minn])
        {
            vis[minn] = true;
            for(int y = 0; y < a[minn].size(); y++)
            {
                int v = a[minn][y].v;
                //cout << v << endl;
                if(vis[v] == false && d[minn] + a[minn][y].dis < d[v])
                {
                    d[v] = d[minn] + a[minn][y].dis;
                    if(!vis[v]) q.push((pri){d[v], v});
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m >> s;
    for(int x = 0; x < m; x++)
    {
        Node tmp;
        int u;
        cin >> u >> tmp.v >> tmp.dis;
        a[u].push_back(tmp);
    }
    Dijkstra();
    for(int x = 1; x <= n; x++) cout << d[x] << " ";
    cout << endl;
    return 0;
}

Floyd

多源最短路

#include <bits/stdc++.h>
#define INF 0x7fffffff
#define MAXN 210
typedef long long LL;
using namespace std;

int n, m;
int d[MAXN][MAXN];
bool findN;

void Floyd()
{
    findN = false;
    for(int z = 0; z < n; z++)
        for(int x = 0; x < n; x++)
            for(int y = 0; y < n; y++)
                if(d[x][z] < INF && d[z][y] < INF)
                    d[x][y] = min(d[x][y], d[x][z] + d[z][y]);
    for(int x = 0; x < n; x++)
        if(d[x][x] < 0) findN = true;
}

int main()
{
    cin >> n >> m;
    for(int x = 0; x < n; x++)
        for(int y = 0; y < n; y++)
            d[x][y] = (x == y ? 0 : INF);

    for(int x = 1; x <= m; x++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);
    }
    Floyd();
    if(findN)
    {
        cout << "NEGATIVE CYCLE" << endl;
        exit(0);
    }
    for(int x = 0; x < n; x++)
    {
        for(int y = 0; y < n-1; y++)
            if(d[x][y] == INF) cout << "INF" << " ";
            else cout << d[x][y] << " ";

        if(d[x][n-1] == INF) cout << "INF" << endl;
        else cout << d[x][n-1] << endl;
    }
    return 0;
}