其实也不算是讲课了...只是把了解的内容整理出来读出来..
其实也不算是明天了..就几个小时以后..睡觉去也~
以下是我写了半天的文档 贻笑大方了
信息学奥赛中的最短路算法
CPY
[写在前面]
最短路算法,是指一类在带权图G=[V,E]中求点对之间最小权值和的路径的算法,是图论算法的重要组成部分.同时由于它与实际问题有着紧密的联系,所以有着广泛的应用.今天我来略讲一下最短路算法.
另外,考虑到竞赛考点的偏向性,本文所讲解的算法,事实上是求最短路的边权和,而要求出这条路径,只须在现有算法基础上略微修改即可实现,不赘述.
[0.预备知识]
[0.1.最优子结构性质]
设P1n是图G=[V,E]中点V1到点Vn的最短路,点Vi与Vj在P1n上,则P1n在点Vi与Vj之间的部分Pij是点Vi与Vj之间的最短路.
[0.2.松弛操作]
设d'[v]是源s到点v之间最短路径的权值上界,对于满足d'[v]>d[u]+w[u,v]的边E[u,v],定义一次松弛操作为d'[v]<--d[u]+w[u,v]的赋值.
下面介绍的Dijkstra算法和Bellman-Ford算法都是建立在松弛的基础上的算法.
[1.SSSP-Single Source Shortest Path 单源最短路]
[1.1.Dijkstra算法]
[1.1.1.算法实现]
令d'[v]=min{d[u]+w[u,v]},每次找出一个使d'[i]最小的点i,令d[i]=d'[i],即求得到源s到i的最短路长度.然后对对于所有以i为起点的边进行松弛操作.将此过程重复n次,就可以得到源s到所有点的最短路长度.
[1.1.2.正确性证明]
由读者完成.
[1.1.3.伪代码]
procedure Dijkstra(Graph,Source)
begin
dis[]<--inf
dis[Source]<--0
queue[]<--Graph-[Source]
while size(queue)<>0 do
begin
for i in queue do
if dis[i]
v<--i
queue<--queue-[v]
for i in queue do
relax(e(v,i))
end
end
[1.1.4.时间复杂度分析与优化]
分析算法可知,朴素的Dijkstra的时间复杂度为O[V^2].在稀疏图中可用二叉堆来存储队列queue,得到O[(V+E)logV]的复杂度.而改用Fibonacci堆存储,可得到O[VlogV+E]的复杂度.但由于Fibonacci堆的实现过于繁琐,所以在竞赛中通常不被使用.
[1.2.Bellman-Ford算法]
[1.2.1.算法实现]
初始时源点d值为0,其余点d值为无穷大.进行V次操作,每次对每条边进行松弛.
[1.2.2.正确性证明]
由读者完成.
[1.2.3.伪代码]
procedure Bellman_Ford(Graph,Source)
begin
dis[]<--inf
dis[Source]<--0
for v do
for e(u,v) do
relax(e(u,v))
end
[1.2.4.时间复杂度分析与优化]
分析知算法复杂度是O[VE].然而实际问题中,通常不需要进行全部V次操作就可得出解,针对此现象,可在每次操作后判断是否在松弛时有赋值操作,若无,可终止算法.这样优化后,复杂度的数学期望可以达到O[ElogV].
[1.3.SPFA-Shortest Path Faster Algorithm]
[1.3.0.简短的说明]
SPFA是Bellman-Ford算法的一种队列实现,优点是减少冗余计算.这里把它作为一种独立的算法提出来讲,
[1.3.1.算法实现]
维护一个队列.初始时队列唯一元素是源点.每次取出队首元素,并松弛以该点为起点的边,将松弛成功的边的终点加入队列.队列为空时算法结束.
[1.3.2.正确性证明]
由读者完成.
[1.3.3.伪代码]
procedure SPFA(Graph,Source)
begin
queue<-[Source]
while size(queue)<>0 do
for i in Graph do
begin
relax(e(queue[start],i))
if relaxed then
queue<-queue+[i]
end
end
[1.3.4.时间复杂度分析]
理论计算表明,SPFA的时间复杂度为O[kE],其中k的数学期望为2.
[1.4.关于以上几种算法]
[1.4.1.小结]
我们已经介绍了求解单源最短路问题的常见算法,现在是一些总结.
由于模型满足最优性原理,上述算法都采用了标号法.标号法是一种优秀的编程思想,在很多类型的问题中都有应用.根据标号的特点可将其分为两种类型.
其一,标号设定算法.在算法的执行过程中不断把临时标号变成永久标号.例如Dijkstra算法.
其二,标号修正算法.算法是迭代的,标号总是临时的.算法思想是不断逼近最优解,只有当算法结束时才能确定想要的结果.例如Bellman-Ford算法.
标号修正算法由于要考虑终止条件与迭代次数,效率通常不如标号设定算法高,也不易被初学者掌握,但它的求解范围通常更广.
[1.4.2.思考]
[1.4.2.1]完成以上两种算法的[正确性证明]
[1.4.2.2]为什么Dijkstra算法不可以处理带有负权边的图?为什么Bellman-Ford算法可以?
[1.4.2.3]对于带有负权回路的图,Bellman-Ford算法该怎样判断?
[1.4.3.可用单源最短路算法求解的问题变体]
[1.4.3.1.单目标最短路问题]将图中的边全部反向,然后求解单源最短路问题.
[1.4.3.2.两点间最短路问题]求解单源最短路问题.目前还未发现比此更优的算法.
[1.4.3.3.所有点对间最短路问题]以每一个点为源,依次求解单源最短路问题.
[2.APSP-All Pairs Shortest Path 多源最短路]
[2.1.Floyd-Warshall算法]
[2.1.0.简介]
考虑最短路的最优子结构性质.设d[i,j,k]是点ij间在点集[1..k]内的最短路长度,那么显然有状态转移方程d[i,j,k]=min(d[i,k,k-1]+d[k,j,k-1],d[i,j,k-1]),边界条件是d[i,j,0]=w(i,j).由于在计算时k是递增的,所以可以忽略第三个维度.这是一种基于动态规划的最短路算法.
[2.1.1.算法实现]
初始时d[i,j]=w(i,j).枚举k,对所有点对ij,检查并更新d[i,j]的值.
[2.1.2.伪代码]
procedure Floyd-Warshall
begin
d[]<--inf
for e(i,j) do
d[i,j]=w(i,j)
for k=1->n do
for i=1->n do
for j=1->n do
d[i,j]=min{d[i,j],d[i,k]+d[k,j]}
end
[2.1.3.时间复杂度分析]
显然算法复杂度为O[V^3]
[2.2.Johnson算法]
[2.2.1.坦白]
据说这算法不是特难,我也很久前就听说过,不过一直没有研究.
目前在竞赛范围内很少有Johnson算法的应用.由于算法实现所需的代码量大,且耗时的优化程度不明显,Johnson算法通常可用Floyd-Warshall算法代替.
这个我没写过.读了wiki的介绍略懂,大概能实现出来,然而还没有熟悉到可以讲出来的程度.所以这算法不讲了....
若有读者对此有兴趣,请参阅wiki上对其的介绍http://en.wikipedia.org/wiki/Johnson's_algorithm
[3.习题]
USACO train Chapter 1 Section 2.4 的5道题目
[4.参考文献]
算法艺术与信息学奥赛 刘汝佳 黄亮 Page304-314
TEXT Shortest Paths USACO Chapter 1 Section 2.4
没有评论:
发表评论