最短路 spfa+STL

与迪杰斯特拉相同的是spfa也是用来求单源点的最短路径问题，但是，当问题中的边是有向负边的时候，迪杰斯特拉就无能为力了，

而且给我的感觉是spfa如何结合STL来用的话代码比迪杰斯特拉的还要短一点，只是在思路上会比它稍微复杂一点点。spfa的原理：

同样设置一个数组d[maxn]用来保存源点到各点的距离，初始化为无穷打，同时定义一个队列que，初始化为空，然后还要定义一个数组visit[maxn]，

用来标记当前的某个点是否在队列当中，初始化为false。算法第一步，把源点加入到队列中，然后用源点去更新源点到它可以到达的点的距离，

如果这个源点到这个点的距离可以被更新，而且队列中没有这个点的话，就把这个点加入到队列中。然后继续从队首弹出一个点，然后同理用这个点

去更新其它的点，重复下去直到队列为空，这时结果就出来了。下面是我A的第一个spfa的代码，用邻接表的，小小的纪念一下。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<deque>

 using namespace std;

 typedef struct node

 {

     int d,len;

     node *next;

 }Linklist;

 typedef struct Node

 {

     int tot;

     Linklist *next;

     Node()

     {

         tot = ;

         next = NULL;

     }

 }linklist;

 linklist rode[];

 int d[],visit[];

 void push(int u,int v,int l)

 {

     Linklist *q = new Linklist;

     q->d = v;

     q->len = l;

     q->next = NULL;

     rode[u].tot++;

     if(rode[u].next == NULL)

     {

         rode[u].next = q;

         return ;

     }

     Linklist *p = rode[u].next;

     while(p->next)

     p = p->next;

     p->next = q;

 }

 int main()

 {

     int n,m,u,v,l;

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

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

     {

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

         push(u,v,l);

     }

     deque<int> que;

     deque<int>::iterator iter;

     que.push_back();

     memset(d,0x3f,sizeof(d));

     memset(visit,,sizeof(visit));

     visit[] = ;

     d[] = ;

     while(!que.empty())

     {

         int temp = *(que.begin());

         que.pop_front();

         visit[temp] = ;

         Linklist *p = rode[temp].next;

         while(p)

         {

             if(d[temp] + p->len < d[p->d])

             {

                 d[p->d] = d[temp] + p->len;

                 if(!visit[p->d])

                 {

                     que.push_back(p->d);

                     visit[p->d] = ;

                 }

             }

             p = p->next;

         }

     }

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

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

     return ;

 }

巴特西

最短路 spfa+STL

最新文章

热门文章