《数学建模图论.》由会员分享，可在线阅读，更多相关《数学建模图论.（19页珍藏版）》请在金锄头文库上搜索。
1、图论一最短路问题问题描述：寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。将问题抽象为赋权有向图或无向图，边上的权均非负对每个顶点定义两个标记（，），其中：表示从顶点到的一条路的权：的父亲点，用以确定最短路的路线：具有永久标号的顶点集1.1Dijkstra算法：即在每一步改进这两个标记，使最终为最短路的权输入：的带权邻接矩阵步骤：（1） 赋初值：令，对，令， 。（2） 对每个 （即不属于上面集合的点），用 代替，这里表示顶点和之间边的权值。计算，把达到这个最小值的一个顶点记为，令。（3） 若，则停
2、止；若，则用代替，转（2）算法结束时，从到各顶点的距离由的最后一次编号给出。在进入之前的编号叫标号，进入之后的编号叫标号。算法就是不断修改各顶点的标号，直至获得标号。若在算法运行过程中，将每一顶点获得标号所由来的边在图上标明，则算法结束时，至各顶点的最短路也在图上标示出来了。理解：贪心算法。选定初始点放在一个集合里，此时权值为0初始点搜索下一个相连接点，将所有相连接的点中离初始点最近的点纳入初始点所在的集合，并更新权值。然后以新纳入的点为起点继续搜索，直到所有的点遍历。Matlab代码：Dijk.mfunctionmydistance,mypath=Dijk(a,sb,db);%sb为起点，d
3、b为终点n=size(a,1);visited(1:n)=0;%n为结点数 visited为结点标号distance(1:n)=inf;distance(sb)=0;%起点到各终点距离的初始化visited(sb)=1;u=sb;%u为新的P标号顶点（初始点）parent(1:n)=0;%父节点的初始化%经过以下一个for.end便可以找到最短路径及该最短路径对应的最短路程for i=1:n-1%(找所有未标号的点) id=find(visited=0);%查找未标号的顶点 for v=id %找到一个未标号的点v if a(u,v)+distance(u)distance(v)%uv之间的距
4、离+起点到u的距离小于 v到起点的距离（第一次是无穷大的，所以第一次肯定满足，下一次则找比这个点到u距离小的v） distance(v)=distance(u)+a(u,v);%修改标号值 则v到原点的距离（权）修改。 parent(v)=u; %u是v的父节点 end end temp=distance;%以上面的distance作为临时的最小距离，如果下一次循环的未标号顶点有更小的距离则替换 temp(visited=1)=inf;%已标号的点距离换为无穷，避免再次搜索 t,u=min(temp);%找出距离最小的点 （t是最小值，u是最小值的下标） 最后一次循环会得到一个最小距离的点 v
5、isited(u)=1;%标记已经标号的顶点end%下面一段代码用于输出pathmypath=;%定义mypath为一个空矩阵if parent(db)=0%如果存在路 =为不等于即前面有parent点 t=db;%终点标号赋给t mypath=db%将终点放入路径集合里 while t=sb%当终点不是初始点 P = parent(t);%终点的父节点令为P mypath=P mypath; t=P;%把上一个点的父节点令为下一轮循环的节点，继续搜索父节点 endendmydistance=distance(db);%最短路程main.mn=29; a=zeros(n);a(1,2)=2;a
6、(1,10)=2;a(1,13)=180;a(1,20)=216;a(1,27)=131;a(2,3)=2;a(3,4)=2;a(4,5)=2;a(5,6)=2;a(6,7)=2;a(6,22)=35;a(7,8)=2;a(8,9)=2;a(9,10)=2;a(11,12)=2;a(12,13)=2;a(13,14)=2;a(13,20)=108;a(14,15)=2;a(15,16)=2; a(16,29)=41;a(17,18)=2;a(18,19)=2;a(18,23)=309; a(18,21)=134;a(19,20)=2;a(20,24)=145;a(20,27)=281;a(20
7、,26)=206;a(21,24)=24;a(22,25)=60;a(22,28)=142;a(23,27)=126;a(24,26)=145;a(26,29)=77;a(28,29)=115;a=a+a; a(a=0)=inf; %把所有零元素替换成无穷a(1:n+1:n2)=0; %对角线元素替换成零，Matlab中数据是逐列存储的for i=1:10mydistance,mypath = Dijk( a,21,i );%从公交南北到A1-A10的最短路径mypathend二floyed算法：2.1基本思想：直接在图的带权邻接矩阵中用插入顶点的方法依次构造出个矩阵、 、，使最后得到的矩阵成
8、为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。2.2基本原理2.2.1求距离矩阵把带权邻接矩作为距离矩阵的初值，即(1)，其中 是从到的只允许作为中间点的路径中最短路的长度(2)，其中 是从到的只允许、作为中间点的路径中最短路的长度%解释：为从；为从 ()，其中是从到的只允许、作为中间点的路径中最短路的长度，即是从到中间可插入任何顶点的路径中最短路的长，因此即是距离矩阵。2.2.2求路径矩阵在建立距离矩阵的同时可建立路径矩阵，的含义是从到的最短路要经过点号为的点， %初值每求得一个时，按下列方式产生相应的新的 即当被插入任何两点间的最短路径时，被记录在中，依次求时求得，可由来查
9、找任何点对之间最短的路径2.2.3查找最短路径若，则点是点到点的最短路的中间点。然后用同样的方法再分头查找。若：(1)向点追溯得：(2)向点追溯得： 步骤：到的距离：到之间的插入点输入：带权邻接矩阵 (1) 赋初值：对所有 (2) 更新对所有，若，则 (3) 若，停止。否则，转(2)Matlab代码：floyed.m%输出最短距离矩阵和最短路径矩阵function d,r=floyd(w)n=length(w);for i=1:n for j=1:n d(i,j)=w(i,j); r(i,j)=j; endendfor k=1:n for i=1:n for j=1:n if d(i,k)+d
10、(k,j)a(i,k)+a(k,j) %如果i,j距离大于从i到k加上从k到j的距离 a(i,j)=a(i,k)+a(k,j) %则i,j距离被更新 path(i,j)=k; %k点加入最短路径 end end endenddist = a(sb,db);%打印pathparent = path(sb,:); %起点到终点最短路上各顶点的父亲点parent(parent=0)=sb; %如果父亲点为0则表示该顶点为起点mypath=db;t=db; %终点放入路径中while t=sb %但某点的父亲点不是不是初始点时，继续循环 p = parent(t); %把该点的父亲点赋给p mypat
11、h = p,mypath; %把p加入path中 t = p; %把p作为新的点继续循环找父亲点的父亲点end可测试数据：n=29; a=zeros(n);a(1,2)=2;a(1,10)=2;a(1,13)=180;a(1,20)=216;a(1,27)=131;a(2,3)=2;a(3,4)=2;a(4,5)=2;a(5,6)=2;a(6,7)=2;a(6,22)=35;a(7,8)=2;a(8,9)=2;a(9,10)=2;a(11,12)=2;a(12,13)=2;a(13,14)=2;a(13,20)=108;a(14,15)=2;a(15,16)=2; a(16,29)=41;a(
12、17,18)=2;a(18,19)=2;a(18,23)=309; a(18,21)=134;a(19,20)=2;a(20,24)=145;a(20,27)=281;a(20,26)=206;a(21,24)=24;a(22,25)=60;a(22,28)=142;a(23,27)=126;a(24,26)=145;a(26,29)=77;a(28,29)=115;a=a+a; a(a=0)=inf; %把所有零元素替换成无穷a(1:n+1:n2)=0; %对角线元素替换成零，Matlab中数据是逐列存储的% for i=1:10d,r=floyd(a)%从公交南北到A1-A10的最短路径% end 二最小生成树在连通赋权图上求权最小的生成树。赋权图的具有最小权的生成树叫做最小生成树。1.Prim算法（贪心算法）图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。构造连通赋权图的最小生成树(是邻接矩阵)，设置两个集合和，其中用于存放的最小生成树
