下载文档原格式
. 图论一．最短路问题问题描绘：找寻最短路径就是在指定网络中两结点间找一条距离最小的路。
最短路不只是指一般地理意义上的距离最短,还能够引申到其他的胸怀,如时间、花费、线路容量等。
将问题抽象为赋权有向图或无向图 G ，边上的权均非负 对每个极点定义两个标记（l(v)，z(v)），此中：l(v)：表示从极点到v 的一条路的权 z(v)：v 的父亲点，用以确立最短路的路线 ：拥有永远标号的极点集算法：即在每一步改良这两个标记，使最后 l(v)为最短路的权 输入：G 的带权毗邻矩阵w(u,v) 步骤： （1） 赋初值：令l(u 0) 0，对v u 0，令 l(v) ，S={u 0}，i 0。
（2）面S 会合的点），用min{l(v),l(u)uS i极点u 和v 之间边的权值。
计算极点记为u i1，令S i1S i（3）w(uv)} 取代l(v)，这里w(uv)表示 l(v)}，把达到这个最小值的一个V1，则停止；若i V1，则用i 1取代i ，转（2）算法结束时，从 u 0到各极点v 的距离由v 的最后一次编号 l(v)给出。
在v 进入S i 以前的编号l(v)叫T 标号，v 进入S i 以后的编号l(v)叫P 标号。
算法就是不停改正各极点的T 标号，直至获取P 标号。
若在算法运转过程中，将每 一极点获取P 标号所由来的边在图上注明，则算法结束时，u 0至各极点的最短路也在图上标示出来了。
理解：贪婪算法。
选定初始点放在一个会合里，此时权值为0初始点搜寻下一个相连结点，将所有相连结的点中离初始点近来的点归入初始点所在的会合，并更新权值。
而后以新归入的点为起点持续搜寻，直到所有的点遍历。
..{u i1}。
若iu Si m in{.Matlab代码：function[mydistance,mypath]=Dijk(a,sb,db);%sb为起点，db为终点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便能够找到最短路径及该最短路径对应的最短行程fori=1:n-1%(找所有未标号的点)id=find(visited==0);%查找未标号的极点forv=id%找到一个未标号的点vifa(u,v)+distance(u)<distance(v)%uv之间的距离+起点到u的距离小于v到起点的距离（第一次是无量大的，所以第一次必定知足，下一次则找比这个点到u距离小的v）distance(v)=distance(u)+a(u,v);%改正标号值则v到原点的距离（权）改正。
数学建模中的图论方法一、引言我们知道，数学建模竞赛中有问题A和问题B。
一般而言，问题A是连续系统中的问题，问题B是离散系统中的问题。
由于我们在大学数学教育内容中，连续系统方面的知识的比例较大，而离散数学比例较小。
因此很多人有这样的感觉，A题入手快，而B题不好下手。
另外，在有限元素的离散系统中，相应的数学模型又可以划分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。
但是这类问题在MCM中非常少见，事实上，由于竞赛是开卷的，参考相关文献，使用现成的算法解决一个P类问题，不能显示参赛者的建模及解决实际问题能力之大小；还有一类所谓的NP问题，这种问题每一个都尚未建立有效的算法，也许真的就不可能有有效算法来解决。
命题往往以这种NPC问题为数学背景，找一个具体的实际模型来考验参赛者。
这样增加了建立数学模型的难度。
但是这也并不是说无法求解。
一般来说，由于问题是具体的实例，我们可以找到特殊的解法，或者可以给出一个近似解。
图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。
应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。
图论方法已经成为数学模型中的重要方法。
许多难题由于归结为图论问题被巧妙地解决。
而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如：AMCM90B－扫雪问题；AMCM91B－寻找最优Steiner树；AMCM92B－紧急修复系统的研制(最小生成树)AMCM94B－计算机传输数据的最小时间(边染色问题)CMCM93B－足球队排名(特征向量法)CMCM94B－锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性)CMCM98B－灾情巡视路线(最优回路)等等。
这里面都直接或是间接用到图论方面的知识。
要说明的是，这里图论只是解决问题的一种方法，而不是唯一的方法。
