最短路径:我的理解--SPFA算法

SPFA算法
  求单源最短路的SPFA算法的全称是:Shortest Path Faster
Algorithm
 最短路径快速算法-SPFA算法是西南交通大学段凡丁于1994年发表的。
  适用范围:给定的图存在负权边,这时类似Dijkstra等算法便没有了用武之地,而Bellman-Ford算法的复杂度又过高,SPFA算法便派上用场了。 我们约定有向加权图G不存在负权回路,即最短路径一定存在。当然,我们可以在执行该算法前做一次拓扑排序,以判断是否存在负权回路,但这不是我们讨论的重点。
  算法思想:我们用数组d记录每个结点的最短路径估计值,用邻接表来存储图G。我们采取的方法是动态逼近法:设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。
最短路径:我的理解--SPFA算法

因为SPFA没有向迪杰斯塔拉算法那样,寻找dist[]的最小值,所以重复入队,更新dis[]的最小值,因为这个点本身dis[]的变化,会影响到与之邻接的点,所以要重复入队。
标程一:
const
int INF =
999999;
int 
map
[MAXN][MAXN];
//map[i,j]为初始输入的ij的距离,未知的map[i,j]=INF;
int 
dis
[MAXN];//源点Si的最短路
char vst[MAXN];//是否在队列中的标记
int     
Q[MAXN];
//队列
//
参数n表示结点数,s表示源点
int SPFA(int n,
int s)
{  int
i, pri, end, p, t;
// pri是队列头结点,end是队列尾结点
   
memset(vst,
0, sizeof(vst));//初始化
   
for(int
i=0; i<</b>MAXN; ++i)
       
Q
[i] =
0;//初始化队列为空
   
for (i=0; i<</b>n; i++)
       
dis
[i] =
INF;//初始化源点到I的值为最大值
   
dis
[s] =
0;//源点为0
   
vst
[s] =
1;//标记为已入队
Q[0] =
s;//源点入队
pri = 0; end
= 1;//队首队尾赋值
   
while (pri
<</b> end)
   
{
       
p
= Q[pri];//取队首元素
       
for (i=0; i<</b>n; ++i)
//更新dis
       
{ if (dis[p]+map[p][i] <</b> dis[i])
           
{ 
dis
[i] =
dis[p]+map[p][i];
               
if (!vst[i])    
//
未在队列中
               
{ 
Q
[end++]
= i;
                  
vst
[i] =
1;
               
}
           
}
       
}
       
vst
[p] =
0;   //

置出队的点为未标记

       
pri
++;
   
}
   
return 1;
}
标程二:
int num[999999]; //记录入队次数
 
void spfa(int s)  // 
初始结点s,即为起点,若目标结点t,则输出dict[t]。
{  
init_data(s);
   
int
head = 0, tail = 1;  
   
int path[Max];  // 
可增加一个path[]数组来记录最后s到t的路径。
    queue[0]
= s; //que.push(s);
 
   
dict[s] = 0;
   
while
(tail >
head)//(!que.empty())
 
    {
int
u = queue[head];//int
u=que.front();  
//que.pop();
       
vis[u] = true;
 
       
for
(i = 1; i <= n; i ++)
       
{ if
(dict[i] > dict[u] +
edge[u][i])
           
{  dict[i] = dict[u] +
edge[u][i];
              
path[i] = u;
 
              
num[i]++
              
if(num[i]>=n) return
1;//判断是否有负权值……
              
if
(!vis[i]) 
//  对以前没有访问过的顶点,加入队列中。
               
{  vis[i] = true;
                  
queue[tail] = i;// que.push(i);
                  
tail
++;                      

 
               
}
            
}
        
}
        
vis[u] = false;  // 
记得把出队列的顶点的vis[]置为false。
       
head ++;
 
   
}
}
判断负权回路
num[i]>=n的原因,即使所有的点更新都会让i入队的话,才只有n-1次,这时一定是最小值了,入队n次,一定有负权回路
上一篇:How to migrate data from another Mac using Mountain Lion and earlier


下一篇:四大算法解决最短路径问题(Dijkstra+Bellman-ford+SPFA+Floyd)