求解最短路的四个算法及其优化

1.Dijkstra算法

Dijkstra很好的运用了贪心算法，其思想是一直找离已加入顶点集合的最短边，更新邻点，下面是实现代码：

<1.朴素Dijkstra算法：

【题意】：给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。

直接Dijkstra即可，注意是有向边，如果是无向边，则需要将两个端点都要存进去，而且数组大小要开两倍！！！；这个图的范围为一个稠密图，适合朴树的Dijkstra算法，其时间复杂度为\(O(v^2)\)；show code:

#include<bits/stdc++.h>

using namespace std;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
struct node
{
    int nex,to,val;
}Edge[maxn];
int head[maxn],n,m,tot=0;
int dis[maxn],v[maxn];
void add(int from,int to,int val)
{
    Edge[++tot].nex=head[from];
    Edge[tot].to=to;
    Edge[tot].val=val;
    head[from]=tot;
}
void Dijkstra(int s)              //s到任一节点的距离
{
    for(int i=0;i<=n;++i)
        dis[i]=(i==s)?0:inf;     //加0方便处理（也可以不加）
    for(int i=1;i<=n;++i)
    {
        int pos=0;
        for(int j=1;j<=n;++j)
            if(!v[j]&&dis[j]<dis[pos])  pos=j;
        v[pos]=1;
        for(int j=head[pos];j!=-1;j=Edge[j].nex)    //找以pos开头的边判断端点是否被访问过
            if(!v[Edge[j].to]&&dis[pos]+Edge[j].val<dis[Edge[j].to]){
                dis[Edge[j].to]=dis[pos]+Edge[j].val;
            }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>m)
    {
        memset(head,-1,sizeof(head));
        for(int i=1;i<=m;++i){
            int a,b,val;
            cin>>a>>b>>val;
            add(a,b,val);
            //add(b,a,val);     //如果是无向图要加上这个
        }
        Dijkstra(1);
        dis[n]==inf?cout<<-1<<endl:cout<<dis[n]<<endl;
    }
}

<2:堆优化的Dijkstra算法

堆优化的Dijkstra算法适合稀疏图，其时间复杂度为\(O(vloge)\)；无向图数组开两倍！！！

还是上面的题意，有自环和重边，求到n号节点的最小值，不存在输出-1.

show code:

#include<bits/stdc++.h>

using namespace std;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
int n,m,head[maxn],dis[maxn],v[maxn],tot=0;
struct Node{
    int dis, pos;           //dis保存距离 pos保存这个dis的点是pos
    Node(int a = 0, int b = 0): dis(a), pos(b) {}
    friend bool operator < (const Node &a, const Node &b){
        return a.dis > b.dis;
    }       //重载小于号， 令dis越大的Node越小，这样优先队列默认按降序排列，top就是dis最小的
    //相当于大根堆变成小根堆
};
struct node
{
    int nex,to,val;
}edge[maxn];

inline void add(int from, int to, int val)
{
    edge[++tot].nex = head[from];
    edge[tot].to = to;
    edge[tot].val = val;
    head[from] = tot;
}
void Dijkstra(int s)
{
    priority_queue<Node> q;          
    for(int i = 1;i <= n; ++i)
        dis[i] = (i == s) ? 0 : inf;
    q.push(Node(0, s));
    while(!q.empty())
    {
        int pos = q.top().pos;      //找到距离最小的点  
        q.pop();                     //找到距离离源点最大的点将它更新一波
        if(v[pos])  continue;
        v[pos] = 1;
        for(int i = head[pos]; i != -1; i = edge[i].nex){
            if(dis[pos] + edge[i].val < dis[edge[i].to])
            {
                dis[edge[i].to] = dis[pos]+edge[i].val;
                q.push(Node(dis[edge[i].to], edge[i].to));  
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin >> n >> m)
    {
        memset(head, -1, sizeof(head));
        memset(v, 0, sizeof(v));
        tot = 0;
        for(int i = 1; i <= m; ++i){
            int a, b, val;
            cin >> a >> b >> val;
            add(a, b, val);
        }
        Dijkstra(1);
        dis[n] == inf ? cout << -1 << endl : cout << dis[n] << endl;
    }
}

2.Floyd算法

Floyd（弗洛伊德）算法的原理是：一直看能不能走别的点使得两点的距离更短(不会组织语言)，其核心思想是区间dp，可以处理带负权的边，其时间复杂度为\(O(v^3)\)看代码：

【题意】：n个点，m条边，q个询问，存在负权和重边，求任意两点之间的最短路径

#include<bits/stdc++.h>

using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=210;
int d[maxn][maxn],n,m,q;
void Floyd()
{
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                if(d[i][k]==inf||d[k][j]==inf)  continue;
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
}

int main()
{
    scanf("%d %d %d",&n,&m,&q);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            d[i][j]=(i==j)?0:inf;       //初始化
    for(int i=1;i<=m;++i){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        d[a][b]=min(d[a][b],c);         //处理重边
    }
    Floyd();
    for(int i=1;i<=q;++i){
        int a,b;
        scanf("%d %d",&a,&b);
        if(d[a][b]==inf)    printf("impossible\n");
        else{
            printf("%d\n",d[a][b]);
        }
    }
}

要想输出路径，其实也很简单，只要在加个Path数组记录一下路径即可：

void Floyd()
{
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            path[i][j]=(d[i][j]==inf)?-1:j;     //初始化路径，输入之后再初始化
    }
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                if(d[i][k]==inf||d[k][j]==inf)  continue;
                if(d[i][j]>d[i][k]+d[k][j]){
                    d[i][j]=d[i][k]+d[k][j];
                    path[i][j]=path[i][k];
                }
            }
}
void print(int start,int end)
{
    printf("%d ",start);
    while(start!=end)
    {
        printf("%d ",path[start][end]);
        start=path[start][end];
    }
}

Floyd还可以用来传递闭包（解不等式）：

void floyd() 
{
    for(int k=1;k<=n;++k){
        for (int i=1;i<=n;++i){
            for (int j=1;j<=n;++j){
                d[i][j]=d[i][j]|(d[i][k]&&d[k][j]);
            }
        }
    }
}

简单用法：题意为求任意两种货币是否可以获益：

#include<bits/stdc++.h>

using namespace std;
const int maxn=100;
string s,temp;
map<string,int> mp;
int n,m,cas=1;
double d[maxn][maxn];
bool Floyd()
{
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                if(d[i][k]==0||d[k][j]==0)  continue;
                if(d[i][j]<d[i][k]*d[k][j])
                    d[i][j]=d[i][k]*d[k][j];
            }
    for(int i=1;i<=n;++i){
        if(d[i][i]>1.0) return true;
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n&&n)
    {
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                d[i][j]=(i==j)?1.0:0;
        for(int i=1;i<=n;++i){
            cin>>temp;
            mp[temp]=i;
        }
        cin>>m;
        string a,b;
        double val;
        for(int i=1;i<=m;++i){
            cin>>a>>val>>b;
            d[mp[a]][mp[b]]=val;
        }
        cout<<"Case "<<cas++<<": ";
        if(Floyd())   cout<<"Yes"<<endl;
        else          cout<<"No"<<endl;
    }
}

3.Bellman-Ford算法

Bellman-Ford是基于迭代思想，它扫描所有的边（x，y，z）,如果：\(dis[y]>dis[x]+z\)，则更新\(dis[y]=dis[x]+z\)，一直到算法结束。

其优点是允许图中存在负权边，且时间复杂度为\(O(ve)\)；

看模板：

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
struct node
{
    int from,to,val;
}edge[maxn];
int  dist[maxn],n,m;                //n为点的个数，m为边的个数
bool Bellman_Ford(int s)
{
    for(int i=1;i<=n;++i)
        dist[i]=(i==s)?0:inf;       //初始化
    for(int i=1;i<n;++i)
        for(int j=1;j<=m;++j){
            if(dist[edge[j].from]+edge[j].val<dist[edge[j].to])
                dist[edge[j].to]=dist[edge[j].from]+edge[j].val;
        }
    bool flag=1;
    // 判断是否有负环路
    for(int i=1;i<=m;++i)
        if(dist[edge[i].to]>dist[edge[i].from]+edge[i].val){
            flag=0;
            break;
        }
    return flag;
}
int main()
{
    scanf("%d%d",&n,&m);       //s为源点
    for(int i=1;i<=m;++i)
        scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].val);
    if(Bellman_Ford(1)&&dist[n]!=inf)
        printf("%d\n",dist[n]);
    else{
        printf("impossible\n");
    }
    system("pause");
}

【题意】：poj-1860 每两种货币之间可以兑换，给定兑换比率和手续费，问能不能通过若干次交换回到原始货币且比原有的货币多。

#include<cstdio>
#include<cstring>
#include<cstdlib>

using namespace std;
const int maxn=1e3+10;
int n,m,s,tot=0;
int de[maxn][2];         //0 start 1 end
double ce[maxn][2];      //0 rate 1 commission
double dis[maxn],v;
bool Bellman_ford(int s)
{
    for(int i=1;i<=n;++i)   dis[i]=0;
    dis[s]=v;
    for(int i=1;i<n;++i){
        int flag=false;
        for(int j=1;j<=tot;++j){
            if(dis[de[j][1]]<(dis[de[j][0]]-ce[j][1])*ce[j][0]){
                dis[de[j][1]]=(dis[de[j][0]]-ce[j][1])*ce[j][0];
                flag=true;
            }
        }
        if(!flag)   return false;
    }
    for(int i=1;i<=tot;++i)
        if(dis[de[i][1]]<(dis[de[i][0]]-ce[i][1])*ce[i][0])     //已经是最大的，如果还能更大的话，说明有正环
            return true;
    return false;
}

int main()
{
    while(~scanf("%d%d%d%lf",&n,&m,&s,&v))
    {
        tot=0;
        for(int i=1;i<=m;++i)
        {
            int a,b;
            double c,d,e,f;
            scanf("%d%d%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f);
            tot++;
            de[tot][0]=a;
            de[tot][1]=b;
            ce[tot][0]=c;
            ce[tot][1]=d;
            tot++;
            de[tot][0]=b;
            de[tot][1]=a;
            ce[tot][0]=e;
            ce[tot][1]=f;
        }
        if(Bellman_ford(s)) printf("YES\n");
        else                printf("NO\n");
    }
    system("pause");
}

4.SPFA算法

SPFA算法又叫做队列优化的Bellman-Ford算法，其时间复杂度为\(O(ke)\)，其中k是一个很小的常数。不过在特殊情况下其时间复杂度会退化到\(O(ev)\)。

它的算法流程和Bellman-Ford类似：先建立一个队列，队列中只包含一个起点s，接着扫描队头所有的出边（x，y，z）,如果：\(dis[y]>dis[x]+z\)，则更新\(dis[y]=dis[x]+z\)，直至算法结束。

裸模板：

#include<bits/stdc++.h>
 
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e5+10;;
int n,m,w;
struct Edge
{
    int nex,to,val;
}edge[maxn];
int head[maxn],dis[maxn],vis[maxn],mark[maxn],tot;
void init()
{
    memset(head,-1,sizeof(head));
    tot=0;
}
void add(int from,int to,int val)
{
    edge[++tot].to=to;
    edge[tot].val=val;
    edge[tot].nex=head[from];
    head[from]=tot;
}
bool SPFA(int s)
{
    for(int i=1;i<=n;i ++){
        mark[i]=0;                  //记录每个点入队列次数
        dis[i]=inf;
        vis[i] = 0;
    }
    queue<int> q;
    q.push(1);                      //我们只需要判断负环，随便找一个起点就好
    dis[s]=0;
    vis[s]=1;//入队列
    mark[s]++;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u] = 0;//出队列
        for(int i=head[u];i!=-1;i=edge[i].nex)
        {
            int v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].val)
            {
                dis[v]=dis[u]+edge[i].val;
                if(!vis[v])                 //不在队列中的时候入队
                {
                    q.push(v);
                    mark[v]++;
                    vis[v]=1;
                }
                if(mark[v]>=n)              //说明存在负环
                    return false;
            }
        }
    }
    return true;
}
int main()
{
    init();
    int u,v,z;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&z);
        add(u,v,z);
    }
    if(SPFA(1)&&dis[n]!=inf)  printf("%d\n",dis[n]);
    else        printf("impossible\n");
}