ch7-3最短路.ppt

1、2020年7月22日星期三，最短路问题，如布局、管道铺设时的选线、设备更新、投资、一个整数修订和动态修订的问题，也可以归结为求最短路的问题。 因此，这种问题在生产中得到了广泛的应用。 求最短路径有两个算法。 一种是用于确定从一个点到另一个点之间的最短距离的索引屈曲(Dijkstra )算法。另一种是用于确定网络上任意两点之间的最短距离的矩阵算法。 最短路的问题是从给定的网状图到各点或任意两点的距离找到最短的路。2020年7月22日星期三，渡河问题，老人想带着大灰狼、羊、白菜从南岸到北岸过河，河里只有一个独木舟。 另外，没有人，狼吃羊，羊吃白菜，如何安排渡河，所有的东西都能渡河，问来往次数最少。

2、 这个问题可以用求最短路的方法解决。m人w狼s羊v白菜、渡河方案共10种，如下图所示。 各边的距离为1，问题是求出与MWSV的最短路。 设北岸、南岸、2020年7月22日星期三、盘结构(Dijkstra )标签条算法、点标签条： b(j )从起点vs到点vj的最短长度、边符号： k(i，j)=b(i) dij、步骤：1.起点的符号。 b(s)0。 求有向图的最短路径，找到网络格拉夫的起点为vs，终点为vt，起点为vj的弧为(I，j )，距离为dij，2 .所有的vi符号vj的无符号弧集合B=(i，j )时，得到这样的弧，3 .集合b中的弧k(i，j )=b (I ) 2020年7月22日星期三

3、，【例】求从下图v1到v7的最短路径和最短路径，0、8、6、2、2、5、4、4、11、14、7、5，从v1到v7的最短路径为11，最短路径为： v1 v4 v6 v7、2020年7月20日由于说明了从起点vs到该点的最短路径及最短距离，因此能够对每个点附加符号，求出从vs到任意点的点符号： b(i )的从起点vs到点vj的最短长度； 边符号： k(i，j)=b(i) dij，步骤：1.作为起点的符号。 b(s)0。 3 .集合b中的边界符号： ki，j=b(i) dij，4 .选择一个点符号：并转到步骤2。 2 .找到所有的一端vi被标签条而另一端vj未被标签条的边集合B=i，并且当不存在该边

4、时、或者当vt被标签条时，校正运算结束。 2020年7月22日星期三，【例】从下图v1各点的最短及最短距离，进入0、4、5、2、2、3、10、3、9、6、12、6、演示和练习，2020年7月22日星期三，具有负权利的最短算法，假定图中没有负电路下图为负电路，最短短路权无下限。 在vi和vj之间没有弧连接的情况下，wij，列表迭代校正：如果vj通过vi从vs到达vj，则从vs到vj的最短距离为：迭代：2020年7月22日星期三，【例】求出从下图v1到v8的最短长度和最短路径1，5，6，2020 2020年7月22日星期三，*任意两点间的最短距离的矩阵算法* (选择)，【例】在下图中用矩阵修正法求出各点间的最短距离，【解】定义dij，2020年7月22日星期三，步骤：1 .2020年7月22日星期三，应用(教材P270例总费用是53。2020年7月22日星期三，最大流问题，作业：教材P284 10.6 1