下载此文档

图论中的几个典型问题上.ppt

文档分类：金融/股票/期货 | 页数：约70页举报非法文档有奖

1/70

下载提示

1.该资料是网友上传的，本站提供全文预览，预览什么样，下载就什么样。
2.下载该文档所得收入归上传者、原创者。
3.下载的文档，不会出现我们的网址水印。

同意并开始全文预览

(约 1-6 秒)

1/70 下载此文档

文档列表 文档介绍

图论中的几类典型问题（上）
：中国邮递员问题，货郎担问题(旅行售货商题Hamilton问题）

1
重要性质：
若v0 v1 … vm 是图G中从v0到vm的最短路, 则1≤k≤m, v0v1 … vk 必为G中从v0到vk的最短路.
即：最短路是一条路，且最短路的任一段也是最短路.
求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，.

2
固定起点的最短路
最短路是一条路径，且最短路的任一段也是最短路．
假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树．
因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路．
3
求赋权图中固定起点的最短路的Dijkstra算法：
4
算法步骤：
5
TO MATLAB
(road1)
6
u1
u2
u3
u4
u5
u6
u7
u8
7
算法的基本思想
返回
求赋权图中任意两点的最短路的Floyd算法：
8
算法原理—— 求距离矩阵的方法
返回
9
算法原理—— 求路径矩阵的方法
在建立距离矩阵的同时可建立路径矩阵R．
即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求时求得，可由来查找任何点对之间最短路的路径．
10

图论中的几个典型问题上来自淘豆网www.taodocs.com转载请标明出处.