对最路径问题的一些研究.docVIP

对最短路径问题的一些研究 赵明阳 【摘要】 图论是信息学奥赛选手必须掌握的知识，而最短路径问题是图论是比较基础的内容，本文对各种不同情况的图中的最短路径作了一些总结。 【关键字】信息学 、最短路径、 Dijkstra、Ford、Bellman-ford、SPFA 图是较线性表和树更为复杂的一种数据结构。 在这种数据结构中，数据节点间的联系是任意的，因此他可以更广泛的表示数据元素之间的关系。图结构在人工智能、数学、物理、化学、计算机科学等许多领域被广泛应用。信息学奥赛的许多试题，也需要用图来描述数据元素之间的联系。最短路径问题就是图论里一个比较重要的算法，下面我就几种不同种类的图，给出不同的求解算法。 一、不带负权回路的图 在带权图G=（V，E）中，若顶点 Vp,Vq是图G的两个顶点，从顶点Vp到Vq的路径长度定义为路径上各条边的权值之和。从顶点Vp到Vq可能有多条路径，其中路径长度最短的一条路径称为顶点Vp到Vq的最短路径。有两类最短路径问题：一是求从某个顶点（源结点）到其它顶点（目的结点）的最短路径问题。这类问题我们称之为单源最短路径问题。二是求图中每一对顶点间的最短路径。 如下例，右图是六个城市之间道路联系的示意图，连线表示两城市间有道路相通，连线旁的数字表示路程。请编写一程序，由计算机找出从C1到C6之间路长最短的一条路径，输出路径序列及总长度。 像这个题目，我们既可以用单源最短路径算法来解决，也可以先求出每对顶点的最短路径，然后输出C1到C6之间的最短路径。 单源最短路径算法当然首推Dijkstra算法。Dijkstra算法的 基本思想是：设置一个顶点的集合s，并不断地扩充这个集合，一个顶点属于集合s当且仅当从源点到该点的路径已求出。开始时s中仅有源点，并且调整非s中点的最短路径长度，找当前最短路径点，将其加入到集合s，直到终点在s中。 主要程序部分如下： ?read(first,tail);? for i:=1 to n do dist[i]:=max; ?dist[first]:=0; ?s:=[first]; u:=first; ?while utail do ?? begin?? for? j:= 1 to n do??? if not(j in s) and (dist[u]+cost[u,j]dist[j]) then???? begin dist[j]:=dist[u]+cost[u,j]; path[j]:=u end;?? min:=max;?? for j:=1 to n do??? if not(j in s) and (dist[j]min) then begin u:=j; min:=dist[j];end;?? if min=max then begin writeln(No answer); halt end;?? s:=s+[u]; ? end; writeln(dist[first,tail]) 这个算法的时间复杂度O（n*n）。 若要求每对点之间的最短路，可以用Ford算法。算法思想为：不停地调整图中的顶点值（源点到该点的最短路径值），直到没有点的值调整了为止。 主要程序段如下： For k:=1 to n do For i：=1 to n do For j:=1 to n do if dis[i,j]dis[i,k]+dis[k,j] then dis[i,j]=dis[i,k]+dis[k,j] writeln(dist[first,tail]) 这个算法的时间复杂度O（n*n*n）,编程复杂度较低。 二、带有负权回路的图 在一个图里每条边都有一个权值（有正有负） ，如果存在一个环（从某个点出发又回到自己的路径），而且这个环上所有权值之和是负数，那这就是一个负权环，也叫负权回路 存在负权回路的图是不能求两点间最短路的，因为只要在负权回路上不断兜圈子，所得的最短路长度可以任意小。对于带有负权回路的图，上面两种算法就不适合用了，那么我们可以采用Bellman-ford算法，算法思想： 1.对每条边进行|V|-1次Relax操作; 2.如果存在(u,v)∈E使得dis[u]+wdis[v],则存在负权回路;否则dis[v]即为s到v的最短距离,pre[v]为前驱。 主要程序段如下： ?For i:=1 to n-1 do ?For j:=1 to e do ? with edges[j] do ?? Relax(a,b,w