Matlab具有较高的运算精度。一般情况下,矩阵类似的运算可以达到数量级的精度,符合一般科学与工程运算的要求。

如果矩阵的条件数很大的话,则矩阵中一个参数的微小变化,就可能会使最终结果发生极大变化,这种现象在数学上称为坏条件问题。对于这类问题,如果没有采用的恰当的算法,最后得出的结果可能不正确。使用Matlab语言一般不会出现这类错误,即是可靠的、数值稳定的。

4  典型图论问题的MATLAB求解

4。1  最短路径问题

最短路径问题是图论中的一个经典问题。最短路径就是从图 中某对顶点 和 之间的全部路径中选出权值之和最小的一条路径作为顶点 到达顶点 的最短路径。这里边的权值可以代表多种含义,如路途、费用、耗时等。文献综述

4。1。1  Dijkstra算法

Dijkstra算法[4]是最短路径的常用算法,是1959年由荷兰计算机科学家E。W。Dijkstra提出的关于最短路径的搜索算法。

Dijkstra算法的基本思想是按距离的从近到远为序,依次求得所有顶点的最短路径和距离,直至算法结束。为避免重复计算并保留每一步计算信息,采用了标号的算法。

下面是该算法的计算步骤：

(1)令 ,对 ,令 , , 。

(2)对所有  ,使用 代替 。当 不相邻时, ,计算 ,把达到这个最小值的顶点记为 ,令 。

(3)若 计算停止；若 ,用 代替 ,转至第2步。

算法结束时,从 到各顶点 的距离使用 最后一次的标号 给出。在 进入 之前的标号 记为 标号, 进入 时的标号 记为 标号。该算法不断修改各顶点的 标号,直至获得 标号。如果在算法运行过程中,将每一顶点获得 标号所由来的边在图上标明,那么在该算法结束时, 至各顶点的最短路径也在图上标示了出来。

Dijkstra算法相应的Matlab的程序如下：

function[d index1 index2]=Dijkf(a)

%a表示图的权值矩阵,d表示所求最短路的权和

%index1表示标号顶点顺序,index2表示标号顶点索引

M=max(max(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;

%更新l(v),同时记录顶点顺序和顶点索引

while sum(pb)<length(a) %重复步骤2,直到满足停止条件

   tb=find(pb==0);

   d(tb)=min(d(tb),d(temp)+a(temp,tb)); %更新l(v)

   tmpb=find(d(tb)==min(d(tb)));

   temp=tb(tmpb(1)); %tmpb可能有多个

   pb(temp)=1;

   index1=[index1,temp];%记录标号顺序

   index=index1(find(d(index1)==d(temp)-a(temp,index1)));

   if length(index)>=2来*自-优=尔,论:文+网www.youerw.com

      index=index(1);

   end

   index2(temp)=index;%记录标号索引

end

d;index1;index2;

应用实例, 是邮递员负责的6条街道,下面矩阵的 号元素是 到 的最短距离,为邮递员制作一张由 到各街道去的最短的路线图。

根据矩阵建立模型如图1所示。

图 1用矩阵 （n为顶点个数）存放各边权的邻接矩阵,行向量pb,index1,index2,d分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值,其中分量

index2存放从始点到第i点最短通路中第i顶点的前一顶点的序号, 存放由始点到第i点最短通路的值。

在Matlab中输入源程序如下：

>> 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); MATLAB图论问题解法研究(3):http://www.youerw.com/shuxue/lunwen_84683.html