最短路问题（各种方法整理）附上一个完美模板

最短路问题（short-path problem），从某点出发到达另一点所经过的路径权值相加最小的一条路径，就是最短路径。

经典的也是最容易掌握的方法Floyd，Dijkstra两种算法。

1.Floyd算法

Floyd算法可以求解的是任意两点的最短路径，功能强大，因此复杂度也很高，但是非常的好懂。

思想很简单，两点的最短路径无非就是直接从一点到另一点，要么就是中间还存在着其他的点。因此只需要暴力枚举中间点，看看存不存在中间路径长度大于直接路径的长度即可。

给出模板（附带记录路径）

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int G[105][105];
int n,m;//n边m点
int next[105][105];
void init()
{
    cin>>n>>m;
    for(int i=0; i<=n; i++)//初始化
    {
        for(int j=0; j<=n; j++)
        {
            if(i==j)
                G[i][j]=G[j][i]=0;
            else G[i][j]=G[j][i]=inf;
        }
    }
    for(int i=0; i<m; i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        if(G[x][y]>w)//有些题目坑人给重复路径
            G[x][y]=G[y][x]=w;
    }
}
void printpath(){
    int st=1,ed=n;
    while(st!=ed){
        cout<<st<<"->";
        st=next[st][ed];
    }
    cout<<ed<<endl;
}
void Floyd()
{
    for(int i=1; i<=n; i++)//初始化路径
        for(int j=1; j<=n; j++)
            next[i][j]=j;

    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(G[i][j]>G[i][k]+G[k][j])
                {
                    G[i][j]=G[i][k]+G[k][j];
                    next[i][j]=next[i][k];
                }
    cout<<G[1][n]<<endl;
    printpath();
}

int main()
{
    init();
    Floyd();
    return 0;
}

代码非常的简洁明了。是最容易弄懂的一个算法。但是复杂度偏高，针对有些题目没必要全部算出最短路，只需要算出单点的最短路。因此有时候复杂度会超限。

2.Dijkstra算法

说实话Dijkstra算法有点像最小生成树，也是开一个数组然后不断更新更新。

Dijkstra算法是先纳入起始点到点集合，然后dis[j]记录的是这个点集合到这个j这个点的距离。因此不断的去纳入新的点，去更新现有的距离。

给出一个带记录路径的模板

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int G[105][105];
int n,m;//n边m点
bool vis[105];
int dis[105],pre[105];
void init()
{
    cin>>n>>m;
    for(int i=0; i<=n; i++)//初始化
    {
        for(int j=0; j<=n; j++)
        {
            if(i==j)
                G[i][j]=G[j][i]=0;
            else G[i][j]=G[j][i]=inf;
        }
    }
    for(int i=0; i<m; i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        if(G[x][y]>w)//有些题目坑人给重复路径
            G[x][y]=G[y][x]=w;
    }
}

void printpath(int v){
    int p=n,cnt=0;
    int ans[105];
    while(p!=v){
        ans[cnt++]=p;
        p=pre[p];
    }
    cout<<v;
    for(int i=cnt-1;i>=0;i--)
        cout<<"->"<<ans[i];
    cout<<endl;
}

void Dijkstra(int v)
{
    int minnum,next;
    for(int i=0; i<=n; i++)
    {
        dis[i]=G[v][i];
        vis[i]=0;
        if(i!=v&&G[v][i]!=inf)
            pre[i]=v;
        else pre[i]=-1;
    }
    vis[v]=1;
    dis[v]=0;
    for(int i=1; i<n; i++) //每次纳入一个点，需要操作n-1次
    {
        minnum=inf;
        for(int j=1; j<=n; j++)//找出距离最小的点当做下一个操作点
        {
            if(!vis[j]&&minnum>dis[j])
            {
                minnum=dis[j];
                next=j;
            }
        }
        if(minnum==inf)
            break;
        vis[next]=1;
        for(int j=1; j<=n; j++) //更新这个操作点到其他点的距离
        {
            if(!vis[j] && G[next][j]!=inf && dis[next]+G[next][j]<dis[j])
            {
                dis[j]=G[next][j]+dis[next];
                pre[j]=next;
            }
        }
    }
    cout<<dis[n]<<endl;
    printpath(v);
}

int main()
{
    init();
    Dijkstra(1);//起始点到最后个点的距离
    return 0;
}

3.Bellman-Ford算法

从百度上弄来的代码，很直观很好理解，对每条边，跑n-1次，每次松弛（妈的，什么叫松弛！？其实就是判断纳入这条边之后对最短路有没有影响，在具体点就是这行代码

dis[edge[j].v] > dis[edge[j].u] + edge[j].cost

）我是不太喜欢那些被装饰的语句的，能简单就简单，能用代码讲清楚的就别搞七搞八。

另spfa是该算法的队列优化

#include<bits/stdc++.h>
using namespace std;
#define MAX 0x3f3f3f3f
#define N 1010

int nodenum, edgenum, original; //点，边，起点

struct Edge //边
{
    int u, v;
    int cost;
};

Edge edge[N];
int dis[N], pre[N];//dis是起点到这个点的最短路，pre存路径

bool Bellman_Ford()
{
    for(int i = 1; i <= nodenum; ++i) //初始化
        dis[i] = (i == original ? 0 : MAX);

    for(int i = 1; i <= nodenum - 1; ++i)//跑这么多次
        for(int j = 1; j <= edgenum; ++j)//每次跑所有的边
            if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛（顺序一定不能反~）
            {
                dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
                pre[edge[j].v] = edge[j].u;
            }
    bool flag = 1; //判断是否含有负权回路
    for(int i = 1; i <= edgenum; ++i)//检验最短路中是否存在负权
        if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)
        {
            flag = 0;
            break;
        }
    return flag;
}

void print_path(int root) //打印最短路的路径（反向）
{
    while(root != pre[root]) //前驱
    {
        printf("%d-->", root);
        root = pre[root];
    }
    if(root == pre[root])
        printf("%d\n", root);
}

int main()
{
    scanf("%d%d%d", &nodenum, &edgenum, &original);//点，边，起点
    pre[original] = original;
    for(int i = 1; i <= edgenum; ++i)
    {
        scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost);
    }
    if(Bellman_Ford())
        for(int i = 1; i <= nodenum; ++i) //起点到每个点最短路
        {
            printf("%d\n", dis[i]);
            printf("Path:");
            print_path(i);
        }
    else
        printf("have negative circle\n");
    return 0;
}

根据pat考试中L2-001题目整理的完美模板，包含一切

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int n,m,st,ed;
int num[505],vis[505],dis[505],pre[505],sum[505],cnt[505];
//每个节点的人数。是否走过。最短距离。前驱。最大救援人数数量.方案数
int G[505][505];//图
void path(int i){
    if(pre[i]!=-1){
        path(pre[i]);
        cout<<pre[i]<<" ";
    }
}
int main()
{
    cin>>n>>m>>st>>ed;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)
                G[i][j]=0;
            else G[i][j]=inf;
        }
    }
    for(int i=0;i<n;i++)
        cin>>num[i];
    for(int i=0;i<m;i++){
        int x,y,w;
        cin>>x>>y>>w;
        G[x][y]=G[y][x]=w;
    }
    memset(dis,inf,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    memset(sum,0,sizeof(sum));
    memset(pre,-1,sizeof(pre));

    dis[st]=0;
    vis[st]=1;
    cnt[st]=1;
    sum[st]=num[st];

    for(int i=0;i<n;i++){
        int minnum=inf,next=st;
        for(int j=0;j<n;j++){
            if(vis[j]==0&&minnum>dis[j]){
                minnum=dis[j];
                next=j;
            }
        }
        vis[next]=1;
        for(int j=0;j<n;j++){
            if(vis[j]==0){
                if(dis[j]>dis[next]+G[next][j]){
                    dis[j]=dis[next]+G[next][j];
                    sum[j]=num[j]+sum[next];
                    cnt[j]=cnt[next];
                    pre[j]=next;
                }
                else if(dis[j]==dis[next]+G[next][j]){
                    cnt[j]=cnt[next]+cnt[j];
                    if(sum[j]<sum[next]+num[j]){
                        sum[j]=sum[next]+num[j];
                        pre[j]=next;
                    }
                }
            }
        }
    }
    cout<<cnt[ed]<<" "<<sum[ed]<<endl;
    path(ed);
    cout<<ed<<endl;
    return 0;
}