其实 提到最短路 应该是先讲Dijkstra 但它的未进行优先队列优化的普通版本与昨天所讲的Prim实在太像了. 所以决定延后几天再讲吧.
今天晚上 去西厂听老蔡和XX 去讲他们的心理路程(找不到好的词语来修饰。。。。) 还是有很多感触的 差距还是很大的. 但往好了想 毕竟我也才大一 是吧？ 还来得及。。。
打完这段话 突然想到了 自欺欺人 这4个字。。。
好了 切回正题。
今天 我们讲的spfa是bellman-ford的优化 关于这个算法最重要的事 应该是它是由我们西南交通大学的段丁凡 提出的.. 当时看到这个 还是很让人振奋的.
它是通过队列进行优化实现的 现在我们就具体来讲讲它的优化实现方式与过程吧
初始化的时候 将源点加入队列 每次从队列中取出一个元素 并将所有与它相邻的点进行松弛操作 若某个相邻的点松弛成功 则将其入队 直到队列中无任何元素为止 over .
可能 你会有疑惑 为什么 松弛成功的点 才能入队呢？
很简单 你可以这样想 如果松弛不成功 那么它与源点的相对距离没有缩减 那么假如有条路径 源点-该点-目标点 是没必要去尝试的 因为我并没有松弛成功 距离没有缩减
这边有必要提下 松弛操作 这个会在我们很多关于图论的算法中涉及到. 譬如上次提过的Prim就运用了它.
松弛--往简单了说 就是刷新该点与源点的最短距离 可能这个解释太过简单了 如果你想更详细的了解 自行百度吧。。
dist[i]表示源点到 I 的当前最短距离
linker[i]表示源点到I的当前最短路径中I点之前的一个点的编号
开始时 dist[i]全部初始化为+∞ 除离自身dist[S]=0 ;
linker[i]全部初始化为S
每次的迭代操作 取出队首V 依次枚举从V出发的边 V->U
判断 dist[v]+map[u][v] 与 dist[u] 的大小关系
若松弛成功 即离源点的相对距离缩短 并且若u不在队列中 就将u入队 放入队尾
这样 重复操作 持续迭代 直至队列为空 即所有点到S的最短路距离 就这样都确定了
特别要提一点 其实spfa并不是我们所讲述的那么好 它是效率不稳定的 一般情况下 我们用Dijkstra就可以解决 遇到任意2点间距离的话 可以用floyd算法 这些我们都会在
后面的随笔中涉及到
接下来 给出它的模板
1 void spfa() 2 { 3 memset( vis, false , sizeof(vis) ); 4 queue<int>qe; 5 for(int i=0;i<n;i++) 6 { 7 dist[i]=inf; 8 } 9 dist[begin]=0; 10 vis[begin]=true; 11 qe.push(begin); 12 while( !qe.empty() ) 13 { 14 int temp=qe.front(); 15 qe.pop(); 16 for(int i=0;i<n;i++) 17 { 18 if( dist[temp] + map[temp][i] < dist[i] ) 19 { 20 dist[i]= dist[temp]+map[temp][i]; 21 if( !vis[i] ) 22 { 23 qe.push(i); 24 vis[i]=true; 25 } 26 } 27 } 28 vis[temp]=false; 29 } 30 }
这里 我并没有给它加以注释 因为我知道 如果你和我一样是初学者 当第一次看到这段代码的时候 即使看了我上面那段 又臭又长的叙述 肯定还是有很多疑惑的 我还是希望
你能去看更加详细的解释 加上 自己的思索 所以 我这边不想加以注释
spfa是我很喜欢的算法 感觉名字很cool。。。。
写完 恰好次日凌晨...