最短路问题

网络图中最短路问题专题研究报告报告人：张鹏学号：20090828班级：035109012011年5月12日网络图中最短路问题【问题导引】网络分析在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要作用。而最短路问题是网络分析中最基本、最关键的问题。最短路径不仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间，费用等等。这些都可以抽像为在图中找出任意两点间的一条通路，使这条通路上的权值和最小。最短路问题作为图与网络技术研究的一个经典问题，在工程规划、地理信息系统、通信和军事运筹学等领域有十分广泛的应用。举例如下：【案例一】：如图的交通网络，图中的点表示交通节点，每条边表示两个节点间的一条通路，边上的数字表示路段的长度，有向边表示单行道，无向边表示可双向行驶。若有一批货物要从1号顶点运往11号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？【案例分析与建模】：这是实际生活中经常遇到的一类问题，首先对该问题做如下假设以便抽象为数学模型。假设一：各路段路况相同，车辆在各路段以相同的速度行驶。假设二：各路段均一路畅通，即不存在堵车问题。102374116598133551122221100661155888877999933222277在以上两种假设的前提下，此问题即转化为在图中选一条从节点1到节点11的通路，使得路径总长度最短，即典型的最短路问题模型。将图抽象为距离矩阵表示，即可建立数学模型，设计算法求解。【算法设计】：对于最短路模型，传统的Dijkstra算法和floyd算法为两种有效的求解方法。利用Dijkstra算法求解案例一中的问题。算法思路：采用标号作业法,每次迭代产生一个永久标号,从而生长一颗以v0为根的最短路树,在这棵树上每个顶点与根节点之间的路径皆为最短路径。S:具有永久标号的顶点集;l(v):v的标记;f(v):v的父顶点,用以确定最短路径;输入：输入加权图的带权邻接矩阵w=[w(vi,vj)]nxm.1）初始化：令l(v0)=0,S=Ø;v≠v0,l(v)=;2）更新l(v),f(v)：寻找不在S中的顶点u,使l(u)为最小.把u加入到S中,然后对所有不在S中的顶点v,如l(v)l(u)+w(u,v),则更新l(v),f(v),即l(v)l(u)+w(u,v),f(v)u;3）重复步骤2),直到所有顶点都在S中为止。这一算法可用于解决满足如下条件的最短路问题：1）寻求从一固定顶点到其余各点的最短路径;2）有向图、无向图和混合图;3）权非负.【程序设计与求解】：根据算法思路，编写程序，借助matlab工具求解。程序：Function[min,path]=dijkstra(w,start,terminal)%定义dijkstra函数%n=size(w,1);label(start)=0;f(start)=start;fori=1:nifi~=startlabel(i)=inf;endends(1)=start;u=start;whilelength(s)nfori=1:nins=0;forj=1:length(s)ifi==s(j)ins=1;endendifins==0v=i;iflabel(v)(label(u)+w(u,v))label(v)=(label(u)+w(u,v));f(v)=u;endendendv1=0;k=inf;fori=1:nins=0;forj=1:length(s)ifi==s(j)ins=1;endendifins==0v=i;ifklabel(v)k=label(v);v1=v;endendends(length(s)+1)=v1;u=v1;endmin=label(terminal);path(1)=terminal;i=1;whilepath(i)~=startpath(i+1)=f(path(i));i=i+1;endpath(i)=start;L=length(path);path=path(L:-1:1);%输入网络图的带权邻接矩阵%edge=[2,3,1,3,3,5,4,4,1,7,6,6,5,5,11,1,8,6,9,10,8,9,9,10;...3,4,2,7,5,3,5,11,7,6,7,5,6,11,5,8,1,9,5,11,9,8,10,9;...3,5,8,5,6,6,1,12,7,9,9,2,2,10,10,8,8,3,7,2,9,9,2,2];n=11;weight=inf*ones(n,n);fori=1:nweight(i,i)=0;endfori=1:size(edge,2)weight(edge(1,i),edge(2,i))=edge(3,i);end[dis,path]=dijkstra(weight,1,11);%调用运函数计算节点1到节点11的最短路径%程序运行结果：dis=%最小距离%21path=%最短路径%1891011即：从节点1到节点11的最短路径为：1→8→9→10→11最短路程为21。【案例一结果分析】：利用dijkstra算法可以有效的解决案例一这一类的问题，而不仅仅是最短距离的问题。若将网络图中的属性变为时间、费用等，就可用同样的方法解决最小时间和最小费用问题。这一类问题统一归结为最短路问题，此处的路是虚指。即：利用Dijkstra算法可以有效解决网络图中任意两点间的最短路径问题。但是，要用Dijkstra算法求解网络图中任意顶点对之间的最短路径，必须轮流以每一个顶点为源点，重复执行算法N次，比较繁琐。下面通过案例二介绍一种更为简洁的算法一次求出任意顶点间的最短距离及路径。【案例二】：某公司在全国十个城市都有分公司，公司成员经常往返与他们之间。各个城市之间的直达航班票价由下表给出（∞表示两城市间无直接航路），，试帮该公司设计一任意两城市间票价最便宜的路线表。各城市直达航班票价表城市123456789101050∞402510∞30181525001520∞25364530553∞1502844∞241216∞4402028027835∞3923525∞4427052543321∞61025∞85203142∞257∞362435543101161588304512∞3342110533791830163921∞6153020101555∞23∞255837200【问题分析】：上述问题是实际生活中经常遇到的一类问题，为了求解上述问题，我们同样先做如下假设。假设：，为了便于购票，接待和休息，以及各分公司之间的交流，公司成员每次出行只能在这十个城市停留，休息，转航班。这样，这个问题就可以归结为赋权网络图的最短路问题，只不过用表格的形式将图呈现出来，这样更利于将其抽象为图的距离矩阵，利用矩阵运算进行数学求解。此案例若要沿用Dijkstra算法解决，需要轮流以每个城市为起点，计算到其他所有城市的最小费用路径。即要多次运行该程序算法，比较繁琐。故本例设计另一算法实现一次即可计算出任意两点间的最短路径。【算法设计】：算法思想及步骤：直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1),D(2),…,D(n),D(n)是图的距离矩阵,同时引入一个后继点矩阵记录两点间的最短路径。d(i,j):i到j的距离;path(i,j):i到j的路径上i的后继点;输入：输入带权邻接矩阵a(i,j).1）赋初值：对所有i,j,d(i,j)a(i,j),path(i,j)j,k=l.2）更新d(i,j),path(i,j)：对所有i,j,若d(i,k)+d(k,j)d(i,j),则d(i,j)d(i,k)+d(k,j),path(i,j)path(i,k),kk+13）重复2)直到k=n+1。利用这一算法可以实现赋权网络图中任意两点间的最短路径问题的求解。【算法的实现】：根据算法思路，编写程序，借助matlab数学工具进行问题的求解。程序：function[D,path,min1,path1]=floyd(a,start,terminal)%编写floyd函数%D=a;n=size(D,1);path=zeros(n,n);fori=1:nforj=1:nifD(i,j)~=infpath(i,j)=j;endendendfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendendifnargin==3min1=D(start,terminal);m(1)=start;i=1;path1=[];whilepath(m(i),terminal)~=terminalk=i+1;m(k)=path(m(i),terminal);i=i+1;endm(i+1)=terminal;path1=m;end【问题求解】：利用上述算法程序，求解案例二中的问题。a=[050inf402510inf301815;5001520inf2536453055;inf1502844inf241216inf;402028027835inf3923;25inf4427052543321inf;%用矩阵形式输入网络图%1025inf85203142inf25;inf36243554310116158;304512inf33421105337;1830163921inf6153020;1555inf23inf255837200];[D,path]=floyd(a)；%引用程序算法求解%D=%最小票价表%03534182510413018153501520472536273043341502837362312163618202802783540362325473727035443321401025368350314028254136233544310113948302712403340110283718301636212839280201543362340254837200path=%最小票价路径矩阵%1696566891062344673949234948899623456736101494518891124416711106284867888133351783101231513391014941688910【案例二结果分析】：由结果可知，floyd算法可有效解决赋权网络图中任意两点间的最短路径问题，且算法简单，只需用矩阵的形式将赋权网络图输入即可输出“最短路”矩阵D及“最短路径矩阵”path。在这两个矩阵中可以查找出任意两点之间的最短“距离’和最短“路径”。例如上述问题中，若要查找城市1到城市三的最小票价和最短路径，只需查D（1，3）=34.最短路径查找path（1，3）=9，path（9，3）=3.即可知最短路径为1→9→3.以此方法查出任意两点间的最短路径即可列出一张表，表示任意两城市间票价最低的路线图。【问题拓展】：以上两个算法虽然可以有效解决网络图中的最短路问题，但现实生活中的问题往往非常复杂的，人们的要求也不是单一的，会随着不同情况发生变化。比如有如下三种情况：1)找到的最短路径或许会由于某种原因行不通，这样人们不仅要求找出最优路径，还想知道次优的，再次的等等，即需要知道前N条最短路。2)两点之间最短路径不唯一时，以上算法只能给出其中一条，无法给出所有的最短路径。3）实际问题中，有时还要求计算任意两点之间含有最少边数的最短路。例如，如果所求网络为实际GIS问题的网络，则节点就表示交叉路口。求最短路的目的之一是用最少时间走完这段路，而交叉路口多会影响行驶的时间。因此，计算任意两点之间含有最少边数情况下的最短路是有实际意义的。因此，上述算法并不能完全满足现实生活中人们的需求，故需对算法进行改进或者重新设计以更好地满足实际需求。但是由于目前知识和能力有限，无法给出有效的算法并用计算机编程实现以解决这一问题。所以，只能通过查阅资料，借鉴他人研