图论-最短路算法总结

目录

1 最短路算法比较

2 Dijkstra（朴素版）

3 Dijkstra（堆优化版）

4 Bellman-Ford

5 SPFA

5.1 SPFA求最短路

5.2 SPFA判断负环

6 Floyd

最短路算法比较

Dijkstra（朴素版）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=510;
ll g[N][N];
ll dist[N];
bool st[N];
ll n,m;
ll dijkstra(){
    memset(dist,0x3f,sizeof dist);            
    dist[1]=0;
    for(ll i=1;i<=n;i++){
        ll t=-1;
        for(ll j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; //在集合v-s中寻找距离顶点距离最小的点
        }
        st[t]=true;
        for(ll j=1;j<=n;j++){
            dist[j]=min(dist[j],dist[t]+g[t][j]);} //用t点更新与t相连的点的距离 判断能否走捷径 一条是自己和顶点 一条是借助t走
    }
    if(dist[n]==0x3f3f3f3f3f3f3f3f) return -1;
    return dist[n];
}
int main(){
   memset(g,0x3f,sizeof g);
   cin>>n>>m;
   while(m--){
        ll a,b,w;
        cin>>a>>b>>w;
        g[a][b]=min(g[a][b],w); //重边取最短
    }
    cout<<dijkstra();
    return 0;
}

Dijkstra（堆优化版）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> Pll;
const ll N = 1e6+10;

ll h[N],w[N],e[2*N],ne[2*N],idx;
ll dist[N];
bool st[N]; // 如果为true说明这个点的最短路径已经确定

ll n, m;
void add(ll a,ll b,ll c){ //将b插入头结点为a的链表中去
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

ll dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    priority_queue<Pll, vector<Pll>, greater<Pll>> heap; // 定义一个小根堆
    // 这里heap中为什么要存pair呢，首先小根堆是根据距离来排的，所以有一个变量要是距离，
    // 其次在从堆中拿出来的时候要知道知道这个点是哪个点，不然怎么更新邻接点呢？所以第二个变量要存点。
    heap.push({ 0, 1 }); // 这个顺序不能倒，pair排序时是先根据first，再根据second，这里显然要根据距离排序
    while(heap.size())
    {
        auto k = heap.top(); // 取不在集合S中距离最短的点
        heap.pop();
        ll ver = k.second, distance = k.first;

        if(st[ver]) continue;
        st[ver] = true;

        for(ll i = h[ver]; i != -1; i = ne[i])
        {
            ll j = e[i]; // i只是个下标，e中在存的是i这个下标对应的点。
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({ dist[j], j });
            }
        }
    }
    // int ==0x3f3f3f3f
    if(dist[n] == 0x3f3f3f3f3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    memset(h, -1, sizeof(h));
    cin>>n>>m;
    while (m--)
    {
        ll a,b,w;
        cin>>a>>b>>w;
        add(a,b,w);
    }

    cout << dijkstra() << endl;

    return 0;
}

Bellman-Ford

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=510;
const ll M=1e5+10;
ll dist[N],backup[N];//dist距离，backup用来存上一次的结果。
ll n,m,k;
struct edge//用来存边
{
    ll a;
    ll b;
    ll w;
}Edge[M];
ll Bellman_Ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(ll i = 0 ; i < k ; i++)
    {
        memcpy(backup,dist,sizeof dist);
        for(ll j = 0 ; j < m ; j++)
        {
            ll a = Edge[j].a, b = Edge[j].b, w = Edge[j].w;
            dist[b] = min(dist[b],backup[a] + w);
        }
    }
    return dist[n];
}
int main(){
    cin>>n>>m>>k;
    for(ll i=0;i<m;i++){
        ll a,b,w;
        cin>>a>>b>>w;
        Edge[i].a=a;
        Edge[i].b=b;
        Edge[i].w=w;
    }
    ll res=Bellman_Ford();
    if(res> 0x3f3f3f3f3f3f3f3f/2) cout<<"impossible";
    else cout<<res;
    return 0;
}

SPFA

SPFA求最短路

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
ll n,m;
ll w[N],h[N],e[N],ne[N],idx;
ll dist[N];
bool st[N];
void add(ll a,ll b,ll c){
    w[idx]=c;
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
ll spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<ll> q;
    q.push(1);
    st[1]=true;
    while(q.size()){
        ll t=q.front();
        q.pop();
        st[t]=false;
        for(ll i=h[t];i!=-1;i=ne[i])
        {
            ll j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                q.push(j);
                st[j]=true;
                }
            }
        }

    }
    return dist[n];
}
int main(){
    cin>>n>>m;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        ll a, b, w;
        cin>>a>>b>>w;
        add(a, b, w);
    }
    ll t = spfa();
    if (t == 0x3f3f3f3f3f3f3f3f) puts("impossible");
    else cout<<t;
    return 0;
}

SPFA判断负环

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
ll n,m;
ll w[N],h[N],e[N],ne[N],idx;
ll dist[N],cnt[N];
bool st[N];
void add(ll a,ll b,ll c){
    w[idx]=c;
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<ll> q;
    for(ll i=1;i<=n;i++){
        st[i]=true;
        q.push(i);
    }
    while(q.size()){
        ll t=q.front();
        q.pop();
        st[t]=false;
        for(ll i=h[t];i!=-1;i=ne[i])
        {
            ll j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n) return true;
                if(!st[j]){
                q.push(j);
                st[j]=true;
                }
            }
        }

    }
    return false;
}
int main(){
    cin>>n>>m;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        ll a, b, c;
        cin>>a>>b>>c;
        add(a, b, c);
    }
    ll t = spfa();
    if (t) puts("Yes");
    else puts("No");
    return 0;
}

Floyd

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=210;
ll n,m,q;
ll d[N][N];
void floyd(){
    for(ll k=1;k<=n;k++){
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=n;j++){
            d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
}
int main(){
    cin>>n>>m>>q;
    memset(d,0x3f,sizeof d);
    for(ll i=1;i<=n;i++) d[i][i]=0;
    while(m--){
        ll a,b,w;
        cin>>a>>b>>w;
        d[a][b]=min(d[a][b],w);
    }
    floyd();
    while(q--){
     ll a,b;
     cin>>a>>b;
     if(d[a][b]>0x3f3f3f3f3f3f3f3f/2) puts("impossible");
     else cout<<d[a][b]<<endl;
    }
    return 0;
}

路径输出 输出 最短路数量 输出路径