最短路算法

我写的Dijkstra最短路算法通用Matlab程序%dijkstra最短路算法通用程序，用于求从起始点s到其它各点的最短路

%D为赋权邻接矩阵，d为s到其它各点最短路径的长度，DD记载了最短路径生成树 function [d,DD]=dijkstra_aiwa(D,s) [m,n]=size(D); d=inf.*ones(1,m); d(1,s)=0; dd=zeros(1,m); dd(1,s)=1; y=s;

DD=zeros(m,m); DD(y,y)=1;

counter=1;

while length(find(dd==1))

if dd(i)==0

d(i)=min(d(i),d(y)+D(y,i)); end end ddd=inf; for i=1:m

if dd(i)==0&&d(i)

yy=find(d==ddd); counter=counter+1; DD(y,yy(1,1))=counter; DD(yy(1,1),y)=counter; y=yy(1,1); dd(1,y)=1; end

function[D,R]=floyd(a)

n=size(a,1); D=a for i=1:n for j=1:n R(i,j)=j; end end R

for k=1:n for i=1:n for j=1:n

if D(i,k)+D(k,j)

例9 某公司在六个城市c1,c2,?,c6中有分公司，从ci到cj的直接航程票价记在下述矩阵的(i,j)位置上。（?表示无直接航路），请帮助该公司设计一张城市c1到其它城市间的票价最便宜的路线图。

?0?50????40??25??105001520?25?1501020?4020100102525?201005510??25???? 25?55??0?2用矩阵an?n（n为顶点个数）存放各边权的邻接矩阵，行向量pb、index1、index、

d分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量

?1pb(i)???0当第i顶点已标号当第i顶点未标号；

index2(i) 存放始点到第i点最短通路中第i顶点前一顶点的序号；

d(i) 存放由始点到第i点最短通路的值。

求第一个城市到其它城市的最短路径的Matlab程序如下： clear; clc;

M=10000;

a(1,:)=[0,50,M,40,25,10];

a(2,:)=[zeros(1,2),15,20,M,25]; a(3,:)=[zeros(1,3),10,20,M];

a(4,:)=[zeros(1,4),10,25];

a(5,:)=[zeros(1,5),55]; a(6,:)=zeros(1,6); a=a+a';

pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=M;d(1)=0;temp=1; while sum(pb)

tb=find(pb==0);

d(tb)=min(d(tb),d(temp)+a(temp,tb)); tmpb=find(d(tb)==min(d(tb))); temp=tb(tmpb(1)); pb(temp)=1;

index1=[index1,temp];

index=index1(find(d(index1)==d(temp)-a(temp,index1))); if length(index)>=2 index=index(1); end

index2(temp)=index; end

d, index1, index2

Floyd算法的Matlab程序如下： clear; clc;

M=10000;

a(1,:)=[0,50,M,40,25,10]; a(2,:)=[zeros(1,2),15,20,M,25]; a(3,:)=[zeros(1,3),10,20,M]; a(4,:)=[zeros(1,4),10,25]; a(5,:)=[zeros(1,5),55]; a(6,:)=zeros(1,6);

b=a+a';path=zeros(length(b)); for k=1:6 for i=1:6 for j=1:6

if b(i,j)>b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j); path(i,j)=k; end end end end

b, path

6.3.2 旅行商（TSP）问题

一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这个问题称为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的Hamilton圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。

一个可行的办法是首先求一个Hamilton圈C，然后适当修改C以得到具有较小权的另一个Hamilton圈。修改的方法叫做改良圈算法。设初始圈C?v1v2?vnv1。

（i）对于1?i?1?j?n，构造新的Hamilton圈: Cij?v1v2?vivjvj?1vj?2?vi?1vj?1vj?2?vnv1,

它是由C中删去边vivi?1和vjvj?1，添加边vivj和vi?1vj?1而得到的。若

w(vivj)?w(vi?1vj?1)?w(vivi?1)?w(vjvj?1)，则以Cij代替C，Cij叫做C的改良圈。

（ii）转（i），直至无法改进，停止。

用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，可以选择不同的初始圈，重复进行几次算法，以求得较精确的结果。

这个算法的优劣程度有时能用Kruskal算法加以说明。假设C是G中的最优圈。则对于任何顶点v，C?v是在G?v中的Hamilton轨，因而也是G?v的生成树。由此推知：若T是G?v中的最优树，同时e和f是和v关联的两条边，并使得w(e)?w(f)尽可能小，则

w(T)?w(e)?w(f)将是w(C)的一个下界。

这里介绍的方法已被进一步发展。圈的修改过程一次替换三条边比一次仅替换两条边更为有效；然而，有点奇怪的是，进一步推广这一想法，就不利了。

例13 从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表：

L M N Pa Pe L 56 35 21 51 M 56 21 57 78 N 35 21 36 68 68 Pa 21 57 36 51 61 Pe 51 78 68 51 13 T 60 70 68 61 13 T 60 70 解：编写程序如下： clc,clear

a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60; a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70; a(3,4)=36;a(3,5)=68;a(3,6)=68; a(4,5)=51;a(4,6)=61;