最短路 spfa 算法 && 链式前向星存图

　　　　 http://blog.csdn.net/mcdonnell_douglas/article/details/54379641

spfa 自行百度说的很详细

spfa 有很多实现的方法 dfs 队列栈都可以时间复杂度也不稳定不过一般情况下要比bellman快得多

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#include <iostream>

#include <sstream>

#include <algorithm>

#include <string>

#include <queue>

#include <ctime>

#include <vector>

using namespace std;

const int maxn= 1e3+;

const int maxm= 1e3+;

const int inf = 0x3f3f3f3f;

typedef long long ll;

int n,m,s;   //n m s 分别表示 点数-标号从1开始 边数-标号从0开始 起点

struct edge

{

    int to,w;

};

int d[maxn];   //d[i]表示 i 点到源点 s 的最短距离

int p[maxn];    //p[i]记录最短路到达 i 之前的节点

int visit[maxn]; // 标记是否已进队

int cnt[maxn];

vector<edge> v[maxn];

int spfa(int x)

{

    queue<int> q;

    memset(visit,,sizeof(visit));

    memset(cnt,,sizeof(cnt));

    for(int i=;i<=n;i++)

        d[i]=inf;

    d[x]=;

    visit[x]=;

    q.push(x);

    while(!q.empty())

    {

        int u=q.front();q.pop();

        visit[u]=;

        for(int i=;i<v[u].size();i++)

        {

            edge &e=v[u][i];

            if(d[u]<inf&&d[u]+e.w<d[e.to])

            {

                d[e.to]=d[u]+e.w;

                p[e.to]=u;

                if(!visit[e.to])

                {

                    q.push(e.to);

                    visit[e.to]=;

                    if(++cnt[e.to]>n)

                        return ;

                }

            }

        }

    }

    return ;

}

void Print_Path(int x)

{

    while(x!=p[x])          //逆序输出 正序的话用栈处理一下就好了

    {

        printf("%d ",x);

        x=p[x];

    }

    printf("%d\n",x);

}

int main()

{

    while(scanf("%d %d %d",&n,&m,&s)!=EOF)

    {

        int x,y,z;

        for(int i=;i<m;i++)

        {

            scanf("%d %d %d",&x,&y,&z);

            edge e;

            e.to=y;

            e.w=z;

            v[x].push_back(e);

//            e.to=x;           //无向图 反向建边

//            v[y].push_back(e);

        }

        p[s]=s;

        if(spfa(s)==)

            for(int i=;i<=n;i++)

            {

                printf("%d %d\n",i,d[i]);

                Print_Path(i);

            }

        else

            printf("sorry\n");

        return ;

    }

}

链式前向星存图

 #include <stdio.h>

 #include <math.h>

 #include <string.h>

 #include <stdlib.h>

 #include <iostream>

 #include <sstream>

 #include <algorithm>

 #include <string>

 #include <queue>

 #include <ctime>

 #include <vector>

 using namespace std;

 const int maxn= 1e3+;

 const int maxm= 1e3+;

 const int inf = 0x3f3f3f3f;

 typedef long long ll;

 int n,m;

 int first[maxn];

 struct edge

 {

     int to,next,w;

 }e[maxn];

 void add(int i,int u,int v,int w)

 {

     e[i].to=v;

     e[i].w=w;

     e[i].next=first[u];

     first[u]=i;

 }

 int main()

 {

     scanf("%d %d",&n,&m);

     {

         int u,v,w;

         memset(first,-,sizeof(first));

         for(int i=;i<m;i++)

         {

             scanf("%d %d %d",&u,&v,&w);

             add(i,u,v,w);

         }

         for(int i=;i<=n;i++)

         {

              cout<<"from"<<i<<endl;

              for(int j=first[i];j!=-;j=e[j].next)  //遍历以j为起点的每条边

                 cout<<"to"<<e[j].to<<" length="<<e[j].w<<endl;

         }

     }

 }

 //输入

 //6 9

 //1 2 2

 //1 4 -1

 //1 3 1

 //3 4 2

 //4 2 1

 //3 6 3

 //4 6 3

 //6 5 1

 //2 5 -1

 //输出

 //from1

 //to3 length=1

 //to4 length=-1

 //to2 length=2

 //from2

 //to5 length=-1

 //from3

 //to6 length=3

 //to4 length=2

 //from4

 //to6 length=3

 //to2 length=1

 //from5

 //from6

 //to5 length=1

秒客网

最短路 spfa 算法 && 链式前向星存图

相关文章