文章2——最短路的其他一些思考

《文章2——最短路的其他一些思考》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最短路问题的其他思考0817010001本文主要思考了次短路问题与过指定点的最短路问题，并对一些问题进行了思考。我们已经学过了最短路问题，我们明白：如果P是Q中从到的最短路，是P中的一个点，那么，从到的路就是到的最短路。然而，而且我们还可以从最短路中得到其他一些思考的东西。一、次短路问题首先，我们可以设想一个情景：在一个军事战斗中，李云龙的部队要分两路从起点A点到终点B点，而此时有许多路径供李云龙挑选。而为了隐蔽性，李云龙分成两个组以不同的路径，从A点到到B点。这就需要我们考虑最短路和次短路了（其实还可以推广到求第三短路等等）。我们来思考次短路问题。我们讨论次短路，首先

2、要知道最短路是怎样的。然后我们得出最短路径是由多少条弧构成的，假设有n条。那么，次短路的思想就来了。我们考虑最短路的n条弧，每次赋值其中1条弧为正无穷，一共需要n次，而每次算出赋值后的最短路，则可以进行对比，从中确定次短路。我们以课本263页的例子分析，我们把它改一下：求点v1到点v8的次短路。根据分析，我们先求出点v1到点v8的最短路，保存在数据文件shortc,程序如下:function[Pu]=shortc(T,t1,t2)n=length(T);D=T;m=1;whilem<=nfori=1:nforj=1:nifD(i,j)>D(i,m)+D(m,j)D(i,

3、j)=D(i,m)+D(m,j);endendendm=m+1;endu=D(t1,t2);P1=zeros(1,n);t=1;P1(t)=t2;V=ones(1,n)*inf;tt=t2;whilett~=t1fori=1:nV(1,i)=D(t1,tt)-T(i,tt);ifV(1,i)==D(t1,i)P1(t+1)=i;tt=i;t=t+1;endendendt=1;x=find(P1~=0);forj=length(x):(-1):1P(t)=P1(x(j));t=t+1;endP;键入：T=[0,6,3,1,inf,inf,inf,inf,inf;inf,0

4、,inf,inf,1,inf,inf,inf,inf;inf,2,0,2,inf,inf,inf,inf,inf;inf,inf,inf,0,inf,10,inf,inf,inf;inf,inf,inf,inf,0,4,3,6,inf;inf,inf,inf,inf,10,0,2,inf,inf;inf,inf,inf,inf,inf,inf,0,4,inf;inf,inf,inf,inf,inf,inf,inf,0,inf;inf,inf,inf,inf,2,inf,inf,3,0];[Pu]=shortb(T,1,8)则输出了P=13258u=12因此我们得到了从1

5、到8的最短路径，然而我们可以继续令上面的各个弧每次都1个为正无穷，从而我们可以得到程序：function[x2d2]=shortz(T)[x1d1]=shortc(T,1,8);n=length(x1);d2=inf;fori=1:(n-1)T(x1(i),x1(i+1))=inf;T(x1(i+1),x1(i))=inf;[kd]=shortb(T,1,8);ifd

6、,inf,inf,inf,inf;inf,inf,inf,0,inf,10,inf,inf,inf;inf,inf,inf,inf,0,4,3,6,inf;inf,inf,inf,inf,10,0,2,inf,inf;inf,inf,inf,inf,inf,inf,0,4,inf;inf,inf,inf,inf,inf,inf,inf,0,inf;inf,inf,inf,inf,2,inf,inf,3,0];[x2d2]=shortz(T)则我们可以得到：x2=1258d2=13这就是从1到8的次短路径与此短路。一、过指定点的最短路问题我们经常看到学校在进行定向越野比赛

7、，每组5人。而定向越野比赛我们知道，怎样合理的安排一组中的每一个成员尽量不走重复的路线，并且在沿途经过眼力去发现要找的包囊，这是最重要的。而我们在找这些包囊时，应该怎样安排呢?尽管最终是从起点到终点，但是经过的次序不一样，用的时间也不同。但这些包囊是必须经过的点。我们可以这样考虑，我们假设v1与v1间只有一个必过点v2，那么自然是从v1到v2再到v1是最短的；我们再考虑v1与v1间有2个必过点v2和v3，那么最短路不是v1到v2到v3到v1,就是v1到v3到v2到v1;这样我们就可以有个初步的想法，先解决v1与v1间有两个点的，再类推其他