首页 > 代码库 > 最短路算法大杂烩

最短路算法大杂烩

2024-07-04 16:55:58   228人阅读

最短路算法主要有以下几个：

一 Dijkstra

二 Bellman-Ford

三 SPFA

四 ASP

五 Floyd-Warshall

 

首先约定一下图的表示：

struct Edge{
         int from,to,wt;
     };
     vector<int>G[N];
     vector<Edge>G[N];

 

-------------Dijkstra算法

使用条件：无负权边

复杂度O：（（V+E）*log（V））

下面是用优先队列实现的Dijkstra算法

//Dijkstra 优先队列版
#include<iostream>
#include<iomanip>
#include<cstring>
#include<stdio.h>
#include<map>
#include<cmath>
#include<algorithm>
#include<vector>
#include<stack>
#include<fstream>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define fab(i,a,b) for(int i=(a);i<=(b);i++)
#define fba(i,b,a) for(int i=(b);i>=(a);i--)
#define MP make_pair
#define PB push_back
#define cls(x) memset(x,0,sizeof(x))
const int INF=0x7ffffff;
using namespace std;
const int N=1005;
struct Edge{
    int from,to,w;
}edges[N];
vector<Edge>G[N];
typedef pair<int,int>PII;

int d[N];
void Dijkstra(int s){
    priority_queue<PII,vector<PII>,greater<PII> >Q;
    fill(d,d+N,INF);
    d[s]=0;
    Q.push(MP(d[s],s));
    while(!Q.empty()){
        PII cur=Q.top();Q.pop();
        int u=cur.second;
        if(cur.first!=u)continue;
        rep(i,G[u].size()){
            int to=G[u][i].to;
            int w=G[u][i].w;
            if(d[to]>d[u]+w){
                d[to]=d[u]+w;
                Q.push(MP(d[to],to));
            }
        }
    }
}

 

-------Bellman-Ford 算法

 

//Bellman-Ford 可判断负权环 
//复杂度O(VE) 
int n;// number of node 
int m;// number of edge
bool Bellman_Ford(int s){
    fill(d,d+N,INF);
    d[s]=0;
    rep(i,n){
        bool update=0;
        rep(j,m){
            Edge &e=edges[j];
            if(d[e.to]>d[e.from]+e.w){
                d[e.to]=d[e.from]+e.w;
                update=1;
            }
        }
        if(!update)return true;
        if(i==n-1&&update)return false;
    }
}

 

------SPFA算法

spfa是对bellman算法的改进，改进了bellman盲目更新的顺序，用类似于dijkstra的队列来更新节点。

基本流程：开始节点s队列，对s的每一个邻接点v更新，如果v不在队列则进队，直到队列为空。如何判断负环呢？因为最短路最多包含V-1条边，因此每一个节点（包括源点s）最多入队V次，所以如果有节点入队V+1次，说明存在负环。

//SPFA  复杂度...据说是O（KE）   k<<V 
bool inqueue[N];
int cnt[N]={0};
bool SPFA(int s){
    queue<int>Q;
    cls(inqueue);
    cls(cnt);
    fill(d,d+N,INF);
    d[s]=0;
    Q.push(s);
    inqueue[s]=1;
    while(!Q.empty()){
        int u=Q.front();Q.pop();
        inqueue[u]=0;
        rep(i,G[u].size()){
            int to=G[u][i].to;
            int w=G[u][i].w;
            if(d[to]>d[u]+w){
                d[to]=d[u]+w;
                if(!inqueue[to]){
                    Q.push(to);
                    inqueue[to]=1;
                    if(++cnt[to]>n)return false;
                }
            }
        }
    }
    return true;
}

------ASP算法

asp算法适用范围小，只能用于有向无环图，思想是dp，按拓扑序列更新节点复杂度O（N）

 

//asp复杂度O(N) 无环 
int ind[N];
void ASP(int s){
    cls(ind);
    fill(d,d+N,INF);
    queue<int>Q;
    Q.push(s);
    rep(i,m)++ind[edges[i].to];
    rep(i,n)if(ind[i]==0)Q.push(i);
    d[s]=0;
    while(!Q.empty()){
        int u=Q.front();Q.pop();
        rep(i,G[u].size()){
            int to=G[u][i].to;
            int w=G[u][i].w;
            if(d[to]>d[u]+w){
                d[to]+d[u]+w;
            }
            if(--ind[to]==0)Q.push(to);
        }
    }
}

 

-----Floyd-Wallshall 多源最短路

 

//多源最短路径 Floyd-Warshall O(N^3)
int d[N][N];
void Floyd_Wallshall(){
    rep(k,n){
       rep(i,n){
            rep(j,n){
                if(d[i][j]>d[i][k]+d[k][j]){
                    d[i][j]=d[i][k]+d[k][j];
                }
            }
       }    
    }
}


联系
我们