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

最短路问题的其他思考 0817010001 本文主要思考了次短路问题与过指定点的最短路问题，并对一些问题进行了思考。 我们已经学过了最短路问题，我们明白：如果P是Q中从到的最短路，是P中的一个点，那么，从到的路就是到的最短路。然而，而且我们还可以从最短路中得到其他一些思考的东西。 次短路问题 首先，我们可以设想一个情景：在一个军事战斗中，李云龙的部队要分两路从起点A点到终点B点，而此时有许多路径供李云龙挑选。而为了隐蔽性，李云龙分成两个组以不同的路径，从A点到到 B点。这就需要我们考虑最短路和次短路了（其实还可以推广到求第三短路等等）。 我们来思考次短路问题。 我们讨论次短路，首先要知道最短路是怎样的。然后我们得出最短路径是由多少条弧构成的，假设有n条。那么，次短路的思想就来了。我们考虑最短路的n条弧，每次赋值其中1条弧为正无穷，一共需要n次，而每次算出赋值后的最短路，则可以进行对比，从中确定次短路。 我们以课本263页的例子分析，我们把它改一下：求点v1到点v8的次短路。根据分析，我们先求出点v1到点v8的最短路，保存在数据文件shortc,程序如下: function [P u]=shortc(T,t1,t2) n=length(T);D=T;m=1; while m=n for i=1:n for j=1:n if D(i,j)D(i,m)+D(m,j) D(i,j)=D(i,m)+D(m,j); end end end m=m+1; end u=D(t1,t2);P1=zeros(1,n);t=1; P1(t)=t2;V=ones(1,n)*inf;tt=t2; while tt~=t1 for i=1:n V(1,i)=D(t1,tt)-T(i,tt); if V(1,i)==D(t1,i) P1(t+1)=i; tt=i; t=t+1; end end end t=1;x=find(P1~=0); for j=length(x):(-1):1 P(t)=P1(x(j)); t=t+1; end P; 键入： T=[0,6,3,1,inf,inf,inf,inf,inf; inf,0,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]; [P u]=shortb(T,1,8) 则输出了 P = 1 3 2 5 8 u = 12 因此我们得到了从1到8的最短路径，然而我们可以继续令上面的各个弧每次都1个为正无穷，从而我们可以得到程序： function [x2 d2]=shortz(T) [x1 d1]=shortc(T,1,8); n=length(x1); d2=inf; for i=1:(n-1) T(x1(i),x1(i+1))=inf; T(x1(i+1),x1(i))=inf; [k d]=shortb(T,1,8); if dd2 d2=d; x2=k; end end 在命令窗口键入： T=[0,6,3,1,inf,inf,inf,inf,inf; inf,0,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]; [x2 d2]=shor