3第三章最短路问题.ppt

v1 [5] v3 v2 v4 v5 v6 [11] 4 5 [4] [8] 0 [12] [6] (b)起点v2 6 11 8 图3.5.2 v1 [24] v3 v2 v4 v5 v6 [15] 23 24 [23] 19 [7] [19] (c)起点v3 0 7 15 图3.5.2 v1 [13] v3 v2 v4 v5 v6 [7] 0 13 [4] 8 [7] [8] (d)起点v4 7 7 4 图3.5.2 v1 [9] v3 v2 v4 v5 v6 [3] 8 9 [8] 4 [3] [4] (e)起点v5 3 3 0 图3.5.2 v1 [17] v3 v2 v4 v5 v6 [8] 16 17 [16] 12 [11] [12] (f)起点v6 11 0 8 图3.5.2 为方便起见，今后我们把从顶点vi到vj的最短路的长度叫做vi到vj的距离，记作d(vi,vj)或d(i,j)． 从上面的六张图虽然可以查出任意一个顶点到另一个顶点的距离，但是这样毕竟不太方便.比较方便的办法是把这些距离集中写在一张象如下的表上．在这张表上，横着排的一行数字叫做“行”，竖着排的一列数字叫做“列”.在表中的第1行上，写的是从v1到各个顶点的距离，同样第2行是v2到各顶点的距离，…….而第1列则是从各个顶点到v1的距离，其余各列也一样. 0 8 16 11 12 17 v6 3 0 8 3 4 9 v5 7 4 0 7 8 13 v4 7 15 23 0 19 24 v3 11 8 4 6 0 5 v2 10 7 3 8 2 0 v1 v6 v5 v4 v3 v2 v1 如上这样的表格叫做图G的距离表，从表上查顶点vi到顶点vj的距离要比从前面的六张图上查容易得多了． 1.2.3 每对顶点之间的最短路 求每对顶点之间最短路的算法是Floyd算法: 1.算法的基本思路: 直接在图的带权邻接矩阵中用插入顶点的方法依次构造出p个矩阵D(1),D(2), …,D(p),使最后得到的矩阵D(p)成为图的距离矩阵,同时也求出插入点矩阵以便得到两点间的最短路径. 2.算法原理: (1)求距离矩阵的方法: 把带权邻接矩阵W作为距离矩阵的初值,即: D(0)=(dij(0))p×p=W 第三章 最短路问题 让我们先把最短路问题的提法明确一下 §3.1 什么是最短路问题 1. 求有向图上的最短路问题：设G=(V,A)是一个有向图，它的每一条弧ai都有一个非负的长度l(ai).在G中指定了两个顶点vs与vt,要求把从vs到vt并且长度最小的有向路找出来． 2. 求无向图上的最短(无向)路问题：设G=(V,E)是一个无向图，它的每一条弧ei都有一个非负的长度l(ei).在G中指定了两个顶点vs与vt,要求把连接vs与vt并且长度最小的(无向)路找出来． 上面两个问题都可以称为最短路问题．很容易看出，这两个问题都有着大量的生产实际背景.事实上，大至海、陆、空各种运输，小至一个人每天上班，都会遇到最短路问题.正因为它用处大，所以近二、三十年来国内外对这个问题进行了不少研究，也找到了许多比较好的计算方法. 有趣的是，有些问题，从表面上看与最短路问题没有什么关系，却可以归结为最短路问题.下面就来举两个这样的例子： 例1 渡河问题：一个人带了一只狼、一只羊和一棵白菜想要过河,河上有一只独木船,每次除了人以外,只能带一样东西.另外,如果人不在旁时,狼就要吃羊,羊就要吃白菜.问应该怎样安排渡河,才能做到把所有东西都带过河去,而且在河上来回的次数又最少. 当然，这个问题不用图论也能解决．大家一眼就能看出，第一次应该带着羊过河，让狼和白菜留下,以下怎么渡法呢？ 下面就来讲一下怎样把这个问题转化成最短路问题． 我们用M代表人，W代表狼，S代表羊，V代表白菜.开始时，设人和其他三样东西都在河的左岸，这种情况，我们用MWSV来表示.又例如人带了羊渡到河的右岸去了，这时左岸留下了狼和白菜，这种情况就用WV来表示.例如MWS表示人(M)狼(W)羊(S)在左岸而白菜(V)在右岸这种情况.那么总共可能有几种允许的情况呢 如果不管狼是否吃羊、羊是否吃白菜，那么总共有16中情况，它们分别是： MWSV, MWS, MWV, MSV, WSV, MW, MS, MV , WS, WV, SV, M, W, S, V, ?(空集) 例如MS表示人和羊在左岸，而狼和白菜在右岸；?表示左岸是空集，即人、狼、羊、白菜都已渡到右岸去了.检查一下就可以知