道客巴巴最短路问题

《道客巴巴最短路问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学建模与数学实验最短路问题实验目的实验内容2．会用MATLAB软件求最短路1．了解最短路的算法及其应用1．图论的基本概念2．最短路问题及其算法3．最短路的应用4．建模案例：最优截断切割问题5．实验作业图论的基本概念一、图的概念1．图的定义2．顶点的次数3．子图二、图的矩阵表示1．关联矩阵2．邻接矩阵返回定义有序三元组G=(V,E,)称为一个图,如果：图的定义定义定义返回顶点的次数例在一次聚会中，认识奇数个人的人数一定是偶数.返回子图返回关联矩阵注：假设图为简单图返回邻接矩阵注：假设图为简单图返回最短路问题及其算法一、基本概念二、固定起点的最短路

2、三、每对顶点之间的最短路返回基本概念返回固定起点的最短路最短路是一条路径，且最短路的任一段也是最短路．假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树．因此,可采用树生长的过程来求指定顶点到其余顶点的最短路．Dijkstra算法：求G中从顶点u0到其余顶点v的最短路.设G为赋权有向图或无向图，G边上的权均非负．对每个顶点v，定义两个标记（l(v)，z(v)），其中:l(v)：表示从顶点u0到v的一条路的权．z(v)：表示v的父亲点，用以确定最短路的路线。算法的过程就是在每一步改进这两个标记，使最终l(v)为从

3、顶点u0到v的最短路的权．S：具有永久标号的顶点集输入:G的带权邻接矩阵w(u,v)算法步骤：TOMATLAB(road1)12345678返回Dijkstra算法w=[0218infinfinfinf%赋权矩阵20inf61infinfinf1inf07infinf9inf8670512infinf1inf503inf9infinfinf13046infinf92inf403infinfinfinf9630]n=size(w,1);%调取行数w1=w(1,:);%选定赋初值fori=1:nl(i)=w1(i);%点u1到各接点的路径长度z(i)

4、=1;%父亲点的序号ends=[];%父亲点集初始化s(1)=1;%选定第一个父亲点u=s(1)%指定父亲点用u表示l%备用儿子节点z%父亲节点k=1;%父亲集中点数初始化whilekl(u)+w(u,i)%如果存在更短路径l(i)=l(u)+w(u,i);%优化顶点i到起点的最短路z(i)=u;%记取i的父节点是uend,end,end,endl,z%求v*ll=l;fori=1:nfor

5、j=1:kifi~=s(j)ll(i)=ll(i);elsell(i)=inf;%父亲节点权令其为infend,end,endlv=inf;%最小值的初值fori=1:nifll(i)

6、403infinfinfinf9630]n=size(w,1);%调取矩阵W的阶数fort=1:nw(t,t)=inf;end%对角线删除零元,变为inf,T1=1;s(1)=T1;%给第一个节点编号为S(1)=1;k=1;Min(T1)=0;Father(T1)=1;%初始化父节点个数为1,%父节点最小值为0,它的父亲编号为1,%以下从其余点中依次找后续父节点whilek

7、小值不在s向量中end,end;D2=inf%最小值初始化;fort1=1:k%k个父项点fort2=1:n%n个子顶点ifw(s(t1),t2)

8、的最小距离'),Min,每对顶点之间的最短路1．求距离矩阵的方法2．求路径矩阵的方法3．查找最短路路径的方法（一）算法的基本思想（三）算