图论中最短路问题的MATLAB程序实现.pdfVIP

维普资讯 20o7年2月 安庆师范学院学报(自然科学版) e、●噙 第13卷第1期 JournalofAnqingTeachersCollege(NaturalScienceEdition) V0L13No．1 图论中最短路问题的MATLAB程序实现 管志忠 1，一，刘永明z (I．池州职业技术学院，安徽池州24700；2．华东师范大学数学系，上海 200062) 摘 要：解决图论中最短路问题的最好方法一 “Dijstra算法”，通过解析实例模型，对模型算法进行描述、拓展，并给出 了求最短路以及求最短路长的MATLAB程序，此程序具有通用性。 关键词：最短路问题；Dkstra算法；MATLAB程序；最短路长 中图分类粤：0157．5 文献标识码：A 文章编号：1007-4260(2007)01—0026—04 1 问题 的提 出 设 G=(V，切为连通 图，顶点集为 {1，2，3，…凡j，图中各边 (i，j)有非负权 cIj(当 (j，j)不是边时 ，权等 于 inf；当(i，i)是有 向边时 ，cii与 Cij可 以不相等)，求一条道路使它是从顶点 1到顶点 凡的所有道路 中总 权数最小的路 ，这就是图论中的最短路 问题 l【】。解决这个 问题至今公认最好的方法是 1959年提出 Di— ikstra算法 ，它用于计算一个点 到其他所有点 的最短路。 此算 法基本原理是 ：若某条路是摄短路 ，这 条路上的任意一段路也是连接这段路两个端点的最短路 ，2】。 2算法描述Ia,卅 第一步 将点s标上永久性标记 )=0，表示从开始点 s到达点$的最短距离是零 。 第二步 将其余的顶点标上 标记 ，记号是试探性标记 ，点_，的T标记 )分两部分 ， )： (，)(O))， 第一部分 T1(f)为从开始点 经过带P标记的点到达 点的最短路的权和 括号中 为第二部分 ，是这 最短路 中，点的前一点 (如有多条最短路 ，则 )可能有多值)。不能经过带 尸标记的点到达的点的 值 ． 是无穷大 (用 inf表示)， 是空集 。 第三步 若这些带有 标记中权和数 ．最小的点是 k，则点 k是带JP标记的点外与开始点 s最近的 点 。把点 k的 标记改为 尸标记 ，如果权和数摄小的点有多个 ，则把它们都改为 尸标记 。若点凡不是 尸 标记 ，转第二步附 带有 标记的点重新标记 ，直至点 为 尸标记为止)。 第四步 追寻最短路，从终点凡开始逆向逐次求最短路经过的点权和为 尸(n)． 从算法直接可见所得到的路是最短路。上述算法更具体的步骤如下：不妨设开始点的标号是 1。 (1股 Ⅳ=0， 1)：0，其余各点都是 标记 ， 值 为无穷大， 值为空集 。 (2)若 Yi点为刚成为 尸标记的(一个或几个1点 ，将所有与这些 ．相邻的带有 标记的点 vj的 标 记的值改为 (y，，N十1)=min[((y，， )’P(v，)+CO~】； 若 T,(vj,N+1)= +c，则 N+I) ，若 T,(vj，N+I)： T，(^D，则 ，N+I)= ^D，(因此 可能是多值的1。 (3)比较所有具有 标记的点 ，把其 中 值最小者的点 的 标记改为 尸标记 ，尸 )=min IV+ l1；当存在两个 以上 的最小者时 ，可 同时将它们改为 P标记 ；若点 凡l则转 (4)，否则将 Ⅳ加一h 1，用 口 代 口f转 网 (2)。 (4)追寻最短路，从终点 凡开始逆 向逐次求最短路经过 的点(可能不止一条最短路)，权和为 尸(凡)。 3 算法拓展与 MATLAB程序 实现 求 凡个顶点 的连通 图 G上任意两点间的最 短路长 的算 法 (它是下面要讲 的F