用matlab寻找赋权图中的最短路中的应用1引言图论是应用数学的一个分支，它的概念和结果来源都非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的格尼斯堡七桥问题，以及在民间广泛流传的一些游戏的难题，如迷宫问题，博弈问题等。
这些古老的难题，吸引了很多学者的注意。
1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的问题时，发挥出很大的作用。
在实践中，图论已成为解决自然科学，工程技术，社会科学，军事等领域中许多问题的有力工具之一。
最短路问题是图论理论中的经典问题，寻找最短路径就是在指定网络中两节点间找一条距离最小的路。
2 最短路2.1 最短路的定义（short-path problem）对最短路问题的研究早在上个世纪60年代以前就卓有成效了，其中对赋权图()0w≥的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法ij能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。
后来海斯在Dijkstra算法的基础之上提出了海斯算法。
但这两种算法都不能解决含有负权的图的最短路问题。
因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。
但在现实生活中,我们所遇到的问题大都不含负权,所以我们在()0ij w≥的情况下选择Dijkstra算法。
若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。
最短路问题是网络理论解决的典型问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管路铺设、线路安装、厂区布局和设备更新等，而且经常被作为一个基本的工具，用于解决其他的做优化问题。
定义1：若图G=G（V，E）中个边[v i ,v j]都赋有一个实数w ij ，则称这样的图G 为赋权图，w ij 称为边[v i ,v j]上的权。
定义2：给定一个赋权有向图，即给一个有向图D=（V,A），对每一个弧a=（v i ,v j），相应地有权w（a）=w ij，又给定D中的两个顶点v s ，v t 。
设P是D中从v s 到v t 的一条路，定义路P的权是P中所有弧的权之和，记为w（P）。
最短路问题就是要在所有从v s到v t 的路中，求一条权最小的路，即求一条从v s到v t 的路P0 ，使w（P0）=min w（P）P式中对D中所有从v s到v t 的路P最小，称P0 是从v s到v t 的最短路。
2.2 最短路问题算法的基本思想及其基本步骤在求解网络图上节点间最短路径的方法中，目前国内外一致公认的比较好的算法有Dijkstra和Floyd算法。
这两种算法，网络被抽象为一个图论中定义的有向图或无向图，并利用图的节点邻接矩阵记录点的关联信息。
在进行图的遍历搜索最短路径时，以该矩阵为基础不断进行目标值的最小性判别，知道获得最后的优化路径。
鉴于课本使用Dijkstra算法，下面用Floyd算法进行计算：设A=（a）n*n 为赋权图G=（V，E，F）的矩阵，当V i V j ∈E时，a ij =F（v i，v j），否则，取a ij =0，a ij =+∞（i≠j），d ij 表示从v i到v j 的点的距离，r ij 表示从v i到v j 的点的最短路中的一个点的编号。
①赋初值。
对所有i，j，d ij = a ij ，r ij =j，k=1，转向②；②更新d ij ，r ij ，对所有i，j，若d ik + d kj < d ij ,则令d ij = d ik + d kj ，r ij =k，转向；③终止判断。
若d ij <0,则存在一条含有顶点v i的负回路，终止；或者k=n，终止；否则，另k=k+1，转向②。
最短路线可由r ij得到。
2.3 用matlab程序实现上述算法编写程序函数程序如下：function f=shortpath(n,A)clear;n=input('请输入矩阵的阶n=');A=input('请输入赋权图对应的n阶矩阵A='); % 顶点之间不通时，用inf表示（MATLAB中，inf 表示无穷）D=A; %赋初值for(i=1:n)for(j=1:n)R(i,j)=j;end;end %赋路径初值for(k=1:n)for(i=1:n)for(j=1:n)if(D(i,k)+D(k,j)<D(i,j))D(i,j)=D(i,k)+D(k,j); %更新dijR(i,j)=k; %更新rijend;end;endk %显示迭代步数D %显示每步迭代后的路长R %显示每步迭代后的路径pd=0;for(i=1:n) %含有负权if(D(i,j)<0)pd=1;break;end;end %存在一条含有顶点的vi的负回路if(pd)break;end %存在一条负回路，终止程序end %程序结束下面用一个实际的例子进行一下函数实际运算：例：求解下赋权图中任意两点中的最短路。
V1 6 V42 6 53 8V08 V2 1 V5 6 v71 72 4 3V39 V5用matlab函数运行以后，运行结果如下：请输入矩阵的阶n=8请输入赋权图对应的n阶矩阵A=[0 2 8 1 inf inf inf inf;2 0 6 inf 1 inf inf inf;8 6 0 7 5 1 2 inf;1 inf 7 0 inf inf 9 inf;inf 1 5 inf 0 3 inf 8;inf inf 1 inf 3 0 4 6;inf inf 2 9 inf 4 0 3;inf inf inf inf 8 6 3 0]k =1D =0 2 8 1 Inf Inf Inf Inf2 0 63 1 Inf Inf Inf8 6 0 7 5 1 2 Inf1 3 7 0 Inf Inf 9 InfInf 1 5 Inf 0 3 Inf 8Inf Inf 1 Inf 3 0 4 6Inf Inf 2 9 Inf 4 0 3Inf Inf Inf Inf 8 6 3 0R =1 2 3 1 5 6 7 81 2 3 4 5 6 7 81 1 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 8k =2D =0 2 8 1 3 Inf Inf Inf2 0 63 1 Inf Inf Inf8 6 0 7 5 1 2 Inf1 3 7 0 4 Inf 9 Inf3 1 54 0 3 Inf 8Inf Inf 1 Inf 3 0 4 6 Inf Inf 2 9 Inf 4 0 3 Inf Inf Inf Inf 8 6 3 0R =1 2 3 1 5 6 7 81 2 3 4 5 6 7 81 1 3 42 6 7 82 23 2 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 8 k =3D =0 2 8 1 3 9 10 Inf2 0 63 1 7 8 Inf8 6 0 7 5 1 2 Inf1 3 7 0 4 8 9 Inf3 1 54 0 3 7 89 7 1 8 3 0 3 610 8 2 9 7 3 0 3Inf Inf Inf Inf 8 6 3 0 R =1 2 3 1 5 3 3 81 2 3 4 5 6 7 81 1 3 423 7 82 23 2 5 6 3 83 3 3 3 5 6 3 83 3 34 3 3 7 81 2 3 4 5 6 7 8 k =4D =0 2 8 1 3 9 10 Inf2 0 63 1 7 8 Inf8 6 0 7 5 1 2 Inf1 3 7 0 4 8 9 Inf3 1 54 0 3 7 89 7 1 8 3 0 3 610 8 2 9 7 3 0 3Inf Inf Inf Inf 8 6 3 0 R =1 2 3 1 5 3 3 81 2 3 4 5 6 7 81 1 3 423 7 82 23 2 5 6 3 83 3 3 3 5 6 3 83 3 34 3 3 7 81 2 3 4 5 6 7 8 k =5D =0 2 8 1 3 6 10 112 0 63 14 8 98 6 0 7 5 1 2 131 3 7 0 4 7 9 123 1 54 0 3 7 86 4 17 3 0 3 610 8 2 9 7 3 0 311 9 13 12 8 6 3 0 R =1 2 3 1 5 5 3 51 2 3 4 5 6 7 51 1 3 42 5 7 52 23 2 5 6 3 85 5 3 5 56 3 83 3 34 3 3 7 85 5 5 5 5678 k = 6D =0 2 7 1 3 6 9 112 0 53 14 7 97 5 0 7 4 1 2 71 3 7 0 4 7 9 123 14 4 0 3 6 86 4 17 3 0 3 69 7 2 9 6 3 0 311 9 7 12 8 6 3 0 R =1 2 6 1 5 5 6 56 6 3 4 6 67 61 1 3 42 5 7 52 2 6 2 5 6 6 85 5 3 5 56 3 86 6 3 4 6 37 85 56 5 5 678 k =7D =0 2 7 1 3 6 9 112 0 53 14 7 97 5 0 7 4 1 2 51 3 7 0 4 7 9 123 14 4 0 3 6 86 4 17 3 0 3 69 7 2 9 6 3 0 311 9 5 12 8 6 3 0 R =1 2 6 1 5 5 6 56 6 3 4 6 67 71 1 3 42 5 7 52 2 6 2 5 6 6 85 5 3 5 56 3 86 6 3 4 6 37 85 5 7 5 5678 k = 8D =0 2 7 1 3 6 9 112 0 53 14 7 97 5 0 7 4 1 2 51 3 7 0 4 7 9 123 14 4 0 3 6 86 4 17 3 0 3 69 7 2 9 6 3 0 311 9 5 12 8 6 3 0 R =1 2 6 1 5 5 6 56 6 3 4 6 67 71 1 3 42 5 7 52 2 6 2 5 6 6 85 5 3 5 56 3 86 6 3 4 6 37 85 5 7 5 567 8注：上例中是用一个无向赋权图，对与有向赋权图只需要把反向的定义为无穷大（在matlab 中即用inf代替不能到达的情况），一样可以调用上述函数程序进行运算。