共有回帖数 0 个
-
图论杂谈系列(一)：单源最短路
话说这个系列春节之前就想写。不过因为过年，大家都懂得，免不了串门什么的，加上自己比较贪玩。不过好在今天晚上终于下决心写完了。
首先来说这个系列的内容，计划图论要写十篇。不过正如题目所述，水平仅限于杂谈。不过也不会像市面上大部分算法书一样泛泛的讲，千篇一律。这些文章只讲一些片面的东西，不过是有启发性的。
其次，本人是哈工程一名大二的学生。专业课没有开，水平也不是很高。知识都是自学的，看经典的算法书和网上大神写的论文。因为没有系统的学习过，谬误或者不严谨的地方肯定会有。所以恳请大家指正。
最后想说的是，这个主要是写一些帮助大家思考的东西，注重思考的过程而不是得出的结论。
对于求单源最短路，我们都知道bellman-ford 和 dijkstra 算法。思考一下bellman-ford算法是如何运行的。没错，对于每一个边都松弛一遍，执行v-1次。如果之后仍然存在边可以松弛，那么说明一定会有负权回路。
代码清单：
for(k=0 ;kn-1; k++)
for(i=0;in;i++)
for(j=0;jn;j++)
if(map[j] inf )
relax (i , j , map[j]);
算法的证明也不难，对于任何一个最短路来说，他一定不会包含回路（不考虑零权回路）。所以他的长度最多是v-1。这样的话，松弛v-1遍，对于每一条路径都可以让它成为最短路径。
那么如何优化这个算法呢，首先我们会想到，如果没有负权回路，那么大多数情况下，它是不用执行v-1遍的。也就是说，执行n遍之后，如果没有边可以松弛的话，这个算法就结束了。所以我们可以加一个辅助变量和一个判断条件。
代码清单：
for(k=0;kn-1;k++)
{
flag = flase;
for(i=0;in;i++)
for(j=0;jn;j++)
if(map[j] inf)
{
relax(i,j,map[j]);
flag=true;
}
if(flag)
break;
}
好的，如果没有负权回路的话，这样优化确实很不错。但是我们不是知足的人，可不可以提前判断是否有负权回路呢？
我们都知道有向图判环的方法。很简单，深搜一遍，找到反向边就可以了。但是如何判断这是不是一个负权回路呢？ 我们这里可以给每一个节点添加一个参数，如果遇到反向边的时候，distdist[v]+cost[e] 的话，那我们就可以确定这是一个负权回路了。下面的代码中，为了表示方便，我们用一个全局变量flag表示是否存在负权回路。
代码清单：
dfs( int x )
{
color[x]=1;
for(i=0;in;i++)
{
if(map[x] inf && color= =0)
{
dist=dist[x]+map[x]
dfs(i);
}
if(map[x] inf && color==1)
if(dist+map[x]dist[x])
flag=true;
}
color[x]=2;
}
如果我们把这样一段程序写在前面，就可以提前判断是否存在负权回路了。
不过这样的话依然存在存在一些并不完美的地方，比如执行第一层循环时如果某个点没有松弛的话，那么下次循环，这个点指向的其他的点依然也不会松弛。只有那些前一遍松弛中改变了距离估计值的点，才能引起他们的邻接点的距离估计值的改变。这样的话可以维持一个队列，让松弛过的点入队列。就有了spfa算法。
我们可以在网上找到很多spfa算法的论文，其中可以看到一种优化方法。就是将距离估计值比较小的点放在队首，比较大的点放在队尾。这里没有用排序或者堆什么的，因为这样确实可以有几率优化，不过仅仅是“几率”。因为让拥有较大距离估计值的节点更容易被松弛，我们显然不希望让已经出队列的点又被松弛又回到了队列中。所以有了这样的一个概率型优化方法。
然后我们分析一下用栈写的spfa算法，这里直接贴我的一段以前写过的c语言代码。
void spfa(int s,int n,int m)
{
int top=0,u,v,e,i;
for(i=1;i=n;i++)
{
vis=0;
dist=inf;
}
dist[s]=0;
stk[top++]=s;
while(top0)
{
u=stk[--top];
vis=0;
for(e=head;e0;e=nxt[e])
{
v=pnt[e];
if(relax(u,v,cost[e]) && vis[v] == 0)
{
vis[v]=1;
stk[top++]=v;
}
}
}
}
为什么用栈写有时候会很快呢？ 首先它很节省空间，因为最多有v-1个节点同时在栈内。其次，它在栈底的点并不容易出栈，所以等到这些节点出栈的时候，它已经被松弛的差不多了。说白了还是一个概率型优化方法。
spfa是一个不稳定的算法，用队列实现有点像广搜。当然大家可以用深搜实现一下。因为即使用栈写，那也是广度优先搜索的思路。因为它是‘一层一层’执行，而深搜是‘一个一个’执行。所以用深搜的思路写，效率可想而知了。
洋洋洒洒，spfa就算说道这里了，后面讲到差分约束的时候还会继续讨论这个算法。
接下来是dijkstra。一个思路很明晰的贪心算法。应用于正权有向图。之所以可以用贪心算法，是因为它是符合矩阵胚系统的。也可以叫做‘拟阵’。其实负权有向图也符合矩阵胚，理论上也可以用贪心算法。但是它没有一个好的选择策略，来判断那个点是已经不可能再松弛的了。所以并没有好的贪心算法去实现。
Dijkstra伪代码：
While(Q!=empty)
{
u=minheap();
s=s+u;
for(all v connected with u)
relax(u,v,cost);
}
这里需要注意relax这个过程是需要进行decrease-heap这个操作的
relax(u,v,cost)
{
if(distdist[v]+cost)
{
dist=dist[v]+cost ;
decrease(u);
}
}
这里不得不提到c++中stl有一个priority queue，是不能直接访问类中元素的。所以不能进行decrease-heap操作。
有一个方法就是在弹出节点的时候进行一次判断，看该节点是不是已经弹出过一次了。不过这样的话，时间复杂度会变成ElogE。
楼主 2015-12-05 12:50 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
