最短路法MATLAB 程序
例1： 某公司在六个城市621,,,c c c 中有分公司，从i c 到j c
的直接航程票价记在下述矩阵的),(j i 位置上。（∞表示无直接航路），请帮助该公司设计一张城市1c 到其它城市间的票价最便宜的路线图。
⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞05525251055010202525100102040
2010015252015050102540500 用矩阵n n a ⨯（n 为顶点个数）存放各边权的邻接矩阵，行向量pb 、
1index 、2index 、d 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量
⎩
⎨⎧=顶点未标号当第顶点已标号当第i i i pb 01)(； )(2i index 存放始点到第i 点最短通路中第i 顶点前一顶点的序号；
)(i d 存放由始点到第i 点最短通路的值。
求第一个城市到其它城市的最短路径的Matlab 程序如下：
程序一：
clc,clear
a=zeros(6); %邻接矩阵初始化
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
a(2,3)=15;a(2,4)=20;a(2,6)=25;
a(3,4)=10;a(3,5)=20;
a(4,5)=10;a(4,6)=25;
a(5,6)=55;
a=a+a'; %将矩阵数据对称赋予矩阵
a(find(a==0))=inf; %找到0值并赋值为inf
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=inf;d(1)=0;
temp=1; %最新的P标号的顶点
while sum(pb)tb=find(pb==0);
d(tb)=min(d(tb),d(temp)+a(temp,tb)); %d指标号顶点索引、
tmpb=find(d(tb)==min(d(tb)));
temp=tb(tmpb(1)); %可能有多个点同时达到最小值，只取其中的一个
pb(temp)=1;
index1=[index1,temp]; %intex1指标号顶点顺序
temp2=find(d(index1)==d(temp)-a(temp,index1));
index2(temp)=index1(temp2(1)); %intex2指标号顶点索引
end
d, index1, index2
程序二
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;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;
end
d
