第三章最短路问题.pptx

上面两个问题都可以称为最短路问题很容易看出，上面两个问题都可以称为最短路问题很容易看出，上面两个问题都可以称为最短路问题很容易看出，上面两个问题都可以称为最短路问题很容易看出，这两个问题都有着大量的生产实际背景这两个问题都有着大量的生产实际背景这两个问题都有着大量的生产实际背景这两个问题都有着大量的生产实际背景.事实上，大至事实上，大至事实上，大至事实上，大至海、陆、空各种运输，小至一个人每天上班，都会遇到海、陆、空各种运输，小至一个人每天上班，都会遇到海、陆、空各种运输，小至一个人每天上班，都会遇到海、陆、空各种运输，小至一个人每天上班，都会遇到最短路问题最短路问题最短路问题最短路问题.正因为它用处大，所以近二、三十年来国正因为它用处大，所以近二、三十年来国正因为它用处大，所以近二、三十年来国正因为它用处大，所以近二、三十年来国内外对这个问题进行了不少研究，也找到了许多比较好内外对这个问题进行了不少研究，也找到了许多比较好内外对这个问题进行了不少研究，也找到了许多比较好内外对这个问题进行了不少研究，也找到了许多比较好的计算方法的计算方法的计算方法的计算方法.有趣的是，有些问题，从表面上看与最短路问题没有趣的是，有些问题，从表面上看与最短路问题没有趣的是，有些问题，从表面上看与最短路问题没有趣的是，有些问题，从表面上看与最短路问题没有什么关系，却可以归结为最短路问题有什么关系，却可以归结为最短路问题有什么关系，却可以归结为最短路问题有什么关系，却可以归结为最短路问题.下面就来举两下面就来举两下面就来举两下面就来举两个这样的例子：个这样的例子：个这样的例子：个这样的例子：例例例例1 1 1 1 渡河问题渡河问题渡河问题渡河问题：一个人带了一只狼、一只羊和一：一个人带了一只狼、一只羊和一：一个人带了一只狼、一只羊和一：一个人带了一只狼、一只羊和一棵白菜想要过河棵白菜想要过河棵白菜想要过河棵白菜想要过河,河上有一只独木船河上有一只独木船河上有一只独木船河上有一只独木船,每次除了人以外每次除了人以外每次除了人以外每次除了人以外,只能带一样东西只能带一样东西只能带一样东西只能带一样东西.另外另外另外另外,如果人不在旁时如果人不在旁时如果人不在旁时如果人不在旁时,狼就要吃羊狼就要吃羊狼就要吃羊狼就要吃羊,羊就要吃白菜羊就要吃白菜羊就要吃白菜羊就要吃白菜.问应该怎样安排渡河问应该怎样安排渡河问应该怎样安排渡河问应该怎样安排渡河,才能做到把所有才能做到把所有才能做到把所有才能做到把所有东西都带过河去东西都带过河去东西都带过河去东西都带过河去,而且在河上来回的次数又最少而且在河上来回的次数又最少而且在河上来回的次数又最少而且在河上来回的次数又最少.当然，这个问题不用图论也能解决大家一眼就当然，这个问题不用图论也能解决大家一眼就当然，这个问题不用图论也能解决大家一眼就当然，这个问题不用图论也能解决大家一眼就能看出，第一次应该带着羊过河，让狼和白菜留下能看出，第一次应该带着羊过河，让狼和白菜留下能看出，第一次应该带着羊过河，让狼和白菜留下能看出，第一次应该带着羊过河，让狼和白菜留下,以下怎么渡法呢？以下怎么渡法呢？以下怎么渡法呢？以下怎么渡法呢？下面就来讲一下怎样把这个问题转化成最短路问题下面就来讲一下怎样把这个问题转化成最短路问题下面就来讲一下怎样把这个问题转化成最短路问题下面就来讲一下怎样把这个问题转化成最短路问题 我们用我们用我们用我们用M M M M代表人，代表人，代表人，代表人，W W W W代表狼，代表狼，代表狼，代表狼，S S S S代表羊，代表羊，代表羊，代表羊，V V V V代表白菜代表白菜代表白菜代表白菜.开始时，设人和其他三样东西都在河的左岸，这种情开始时，设人和其他三样东西都在河的左岸，这种情开始时，设人和其他三样东西都在河的左岸，这种情开始时，设人和其他三样东西都在河的左岸，这种情况，我们用况，我们用况，我们用况，我们用MWSVMWSVMWSVMWSV来表示来表示来表示来表示.又例如人带了羊渡到河的右又例如人带了羊渡到河的右又例如人带了羊渡到河的右又例如人带了羊渡到河的右岸去了，这时左岸留下了狼和白菜，这种情况就用岸去了，这时左岸留下了狼和白菜，这种情况就用岸去了，这时左岸留下了狼和白菜，这种情况就用岸去了，这时左岸留下了狼和白菜，这种情况就用WVWVWVWV来表示来表示来表示来表示.例如例如例如例如MWSMWSMWSMWS表示人表示人表示人表示人(M)(M)(M)(M)狼狼狼狼(W)(W)(W)(W)羊羊羊羊(S)(S)(S)(S)在左岸而白菜在左岸而白菜在左岸而白菜在左岸而白菜(V)(V)(V)(V)在右岸这种情况在右岸这种情况在右岸这种情况在右岸这种情况.那么总共可能有几种允许的情况那么总共可能有几种允许的情况那么总共可能有几种允许的情况那么总共可能有几种允许的情况呢呢呢呢 如果不管狼是否吃羊、羊是否吃白菜，那么总共如果不管狼是否吃羊、羊是否吃白菜，那么总共如果不管狼是否吃羊、羊是否吃白菜，那么总共如果不管狼是否吃羊、羊是否吃白菜，那么总共有有有有16161616中情况，它们分别是：中情况，它们分别是：中情况，它们分别是：中情况，它们分别是：MWSV,MWS,MWV,MSV,WSV,MW,MWSV,MWS,MWV,MSV,WSV,MW,MS,MV,WS,WV,SV,M,W,S,V,MS,MV,WS,WV,SV,M,W,S,V,(空集空集空集空集)例如例如例如例如MSMS表示人和羊在左岸，而狼和白菜在右岸；表示人和羊在左岸，而狼和白菜在右岸；表示人和羊在左岸，而狼和白菜在右岸；表示人和羊在左岸，而狼和白菜在右岸；表表表表示左岸是空集，即人、狼、羊、白菜都已渡到右岸去示左岸是空集，即人、狼、羊、白菜都已渡到右岸去示左岸是空集，即人、狼、羊、白菜都已渡到右岸去示左岸是空集，即人、狼、羊、白菜都已渡到右岸去了了了了.检查一下就可以知道，这检查一下就可以知道，这检查一下就可以知道，这检查一下就可以知道，这1616种情况中有种情况中有种情况中有种情况中有6 6种情况是不种情况是不种情况是不种情况是不允许出现的允许出现的允许出现的允许出现的.分别是：分别是：分别是：分别是：WSV,MW,MV,WS,SV,M.WSV,MW,MV,WS,SV,M.例例例例如如如如WSVWSV表示狼、羊、白菜都在左岸而人在右岸，因为表示狼、羊、白菜都在左岸而人在右岸，因为表示狼、羊、白菜都在左岸而人在右岸，因为表示狼、羊、白菜都在左岸而人在右岸，因为人不在旁边看着人不在旁边看着人不在旁边看着人不在旁边看着,狼就要吃羊，羊也要吃白菜；又如狼就要吃羊，羊也要吃白菜；又如狼就要吃羊，羊也要吃白菜；又如狼就要吃羊，羊也要吃白菜；又如MVMV表示人和白菜在左岸，而狼和羊在右岸，当然也是表示人和白菜在左岸，而狼和羊在右岸，当然也是表示人和白菜在左岸，而狼和羊在右岸，当然也是表示人和白菜在左岸，而狼和羊在右岸，当然也是不行的不行的不行的不行的.因此，允许出现的情况只有因此，允许出现的情况只有因此，允许出现的情况只有因此，允许出现的情况只有1010种种种种.现在我们就来构造一个图现在我们就来构造一个图现在我们就来构造一个图现在我们就来构造一个图G G G G，它的顶点就是这，它的顶点就是这，它的顶点就是这，它的顶点就是这10101010种种种种情况，情况，情况，情况，G G G G中的边是按照下述原则来连的；如果情况甲中的边是按照下述原则来连的；如果情况甲中的边是按照下述原则来连的；如果情况甲中的边是按照下述原则来连的；如果情况甲经过一次渡河可以变成情况乙，那么就在情况甲与乙经过一次渡河可以变成情况乙，那么就在情况甲与乙经过一次渡河可以变成情况乙，那么就在情况甲与乙经过一次渡河可以变成情况乙，那么就在情况甲与乙之间连一条边之间连一条边之间连一条边之间连一条边.WVWVWWS SV VMWSMWSMWVMWVWSVWSVMSMSMWSVMWSV 例如，例如，例如，例如，MWSVMWSVMWSVMWSV经过一次渡河可以变成经过一次渡河可以变成经过一次渡河可以变成经过一次渡河可以变成WV(WV(WV(WV(人带着羊过人带着羊过人带着羊过人带着羊过河，左岸留下狼和白菜河，左岸留下狼和白菜河，左岸留下狼和白菜河，左岸留下狼和白菜)，又例如，又例如，又例如，又例如MWVMWVMWVMWV经过一次渡河可经过一次渡河可经过一次渡河可经过一次渡河可以变为以变为以变为以变为W(W(W(W(人带着白菜过河，留下狼人带着白菜过河，留下狼人带着白菜过河，留下狼人带着白菜过河，留下狼)，或变为，或变为，或变为，或变为V.V.V.V.当然当然当然当然反过来，反过来，反过来，反过来，W W W W也可以变为也可以变为也可以变为也可以变为MWV(MWV(MWV(MWV(人带着白菜从右岸返回左人带着白菜从右岸返回左人带着白菜从右岸返回左人带着白菜从右岸返回左岸岸岸岸).).).).作出了图作出了图作出了图作出了图GG以后，渡河问题就归结为下述问题了：以后，渡河问题就归结为下述问题了：以后，渡河问题就归结为下述问题了：以后，渡河问题就归结为下述问题了：“在图在图在图在图GG中找一条连接顶点中找一条连接顶点中找一条连接顶点中找一条连接顶点MWSVMWSV与与与与，并且包含边数，并且包含边数，并且包含边数，并且包含边数最少的路最少的路最少的路最少的路”.如果我们设如果我们设如果我们设如果我们设GG的每条边的长度都是的每条边的长度都是的每条边的长度都是的每条边的长度都是1 1，那么，那么，那么，那么也可以把渡河问题归结为：也可以把渡河问题归结为：也可以把渡河问题归结为：也可以把渡河问题归结为：“找一条连接找一条连接找一条连接找一条连接MWSVMWSV与与与与的最短路的最短路的最短路的最短路”.例例2:某两人有一只某两人有一只8升的酒壶装满了酒，还有两只升的酒壶装满了酒，还有两只空壶，分别为空壶，分别为5升和升和3升升.现要将酒平分，求最少的现要将酒平分，求最少的操作次数操作次数.解解 设设x1,x2,x3分别表示分别表示8,5,3升酒壶中的酒量升酒壶中的酒量.则则容易算出容易算出(x1,x2,x3)的组合形式共的组合形式共24种种.(0,5,3);(1,5,2);(1,4,3);(2,5,1);(2,4,2);(2,3,3);(3,5,0);(3,4,1);(3,3,2);(3,2,3);(4,4,0);(4,3,1);(4,2,2);(4,1,3);(5,3,0);(5,2,1);(5,1,2);(5,0,3);(6,2,0);(6,1,1);(6,0,2);(7,1,0);(7,0,1);(8,0,0);于是问题转化为在该图中求于是问题转化为在该图中求(8,0,0)到到(4,4,0)的一条最短的一条最短路路(求最短路的算法在有向图中仍适用求最短路的算法在有向图中仍适用).结果如下：结果如下：每种组合用一个点表示，若点每种组合用一个点表示，若点u能通过倒酒的方式变能通过倒酒的方式变换为换为v,则则 u向向v 连有向边，并将各边赋权连有向边，并将各边赋权1，得一个有向，得一个有向赋权图赋权图.大家也许会认为，这两个例子本来就不很难，把大家也许会认为，这两个例子本来就不很难，把大家也许会认为，这两个例子本来就不很难，把大家也许会认为，这两个例子本来就不很难，把它转化成图论问题，倒相当麻烦，有什么好处呢？其它转化成图论问题，倒相当麻烦，有什么好处呢？其它转化成图论问题，倒相当麻烦，有什么好处呢？其它转化成图论问题，倒相当麻烦，有什么好处呢？其实这种做法还是很有好处的实这种做法还是很有好处的实这种做法还是很有好处的实这种做法还是很有好处的.因为在转化前，想解决因为在转化前，想解决因为在转化前，想解决因为在转化前，想解决这些问题，只能用凑的办法，或者最多是凭经验这些问题，只能用凑的办法，或者最多是凭经验这些问题，只能用凑的办法，或者最多是凭经验这些问题，只能用凑的办法，或者最多是凭经验.而而而而转化成图论问题以后，就可以用一种系统的方法解决转化成图论问题以后，就可以用一种系统的方法解决转化成图论问题以后，就可以用一种系统的方法解决转化成图论问题以后，就可以用一种系统的方法解决了了了了.最后，还要指出一下，求最短有向路和求最短无最后，还要指出一下，求最短有向路和求最短无最后，还要指出一下，求最短有向路和求最短无最后，还要指出一下，求最短有向路和求最短无向路这两个问题是密切关联的向路这两个问题是密切关联的向路这两个问题是密切关联的向路这两个问题是密切关联的.下面将看到，求最短有下面将看到，求最短有下面将看到，求最短有下面将看到，求最短有向路的计算方法也可以用来求最短无向路向路的计算方法也可以用来求最短无向路向路的计算方法也可以用来求最短无向路向路的计算方法也可以用来求最短无向路.在这一章中，我们假设遇到的图在这一章中，我们假设遇到的图在这一章中，我们假设遇到的图在这一章中，我们假设遇到的图G G G G都是简单图都是简单图都是简单图都是简单图.这这这这样假设是合理的，因为如果样假设是合理的，因为如果样假设是合理的，因为如果样假设是合理的，因为如果G G G G有平行弧或平行边，例有平行弧或平行边，例有平行弧或平行边，例有平行弧或平行边，例如有好几条从如有好几条从如有好几条从如有好几条从v v v vi i i i到到到到v v v vj j j j的弧，那么很显然，可以把这些的弧，那么很显然，可以把这些的弧，那么很显然，可以把这些的弧，那么很显然，可以把这些弧中最短的一条留下，其余的都去掉，然后在剩下的弧中最短的一条留下，其余的都去掉，然后在剩下的弧中最短的一条留下，其余的都去掉，然后在剩下的弧中最短的一条留下，其余的都去掉，然后在剩下的简单图上再来求从简单图上再来求从简单图上再来求从简单图上再来求从v v v vs s s s到到到到v v v vt t t t的最短有向路的最短有向路的最短有向路的最短有向路.因为因为因为因为G G G G是简单是简单是简单是简单图，所以每一条弧图，所以每一条弧图，所以每一条弧图，所以每一条弧a a a ak k k k被它的起点被它的起点被它的起点被它的起点v v v vi i i i与终点与终点与终点与终点v v v vj j j j唯一决定，唯一决定，唯一决定，唯一决定，因此，下面我们就用因此，下面我们就用因此，下面我们就用因此，下面我们就用vvv 或或或或来表示一条弧，来表示一条弧，来表示一条弧，来表示一条弧，用用用用(v(v(v(vi i i i,v,v,v,vj j j j)或或或或(i,j)(i,j)(i,j)(i,j)来表示边，而用来表示边，而用来表示边，而用来表示边，而用l(i,j)l(i,j)l(i,j)l(i,j)来表示弧或来表示弧或来表示弧或来表示弧或边的长度边的长度边的长度边的长度.这一节介绍一种求有向图上最短有向路的方这一节介绍一种求有向图上最短有向路的方法，叫做法，叫做标号法。标号法。3.2 求最短有向路的标号法求最短有向路的标号法 所谓标号所谓标号,我们是指与图的每一个顶点对应的一个我们是指与图的每一个顶点对应的一个数数(或几个数或几个数)例如设例如设G=(V,A)的顶点集合是的顶点集合是V=v1,v2,vn，如果我们能使，如果我们能使v1对应一个数对应一个数b(1)，v2对应数对应数b(2)，vn对应数对应数b(n)，那么，这些数，那么，这些数b(i)就称为就称为vi的标的标号，当然，在不同的问题中，标号号，当然，在不同的问题中，标号b(i)一般代表不同的一般代表不同的意义意义.回到我们要解决的最短有向路问题上来回到我们要解决的最短有向路问题上来回到我们要解决的最短有向路问题上来回到我们要解决的最短有向路问题上来.为确定起为确定起为确定起为确定起见，我们设见，我们设见，我们设见，我们设v v v vs s s s=v=v=v=v1 1 1 1，v v v vt t t t=v=v=v=vn n n n,也就是说我们要找的是从也就是说我们要找的是从也就是说我们要找的是从也就是说我们要找的是从v v v v1 1 1 1到到到到v v v vn n n n的最短有向路的最短有向路的最短有向路的最短有向路.下面介绍的方法可以把从下面介绍的方法可以把从下面介绍的方法可以把从下面介绍的方法可以把从v v v v1 1 1 1到到到到G G G G的的的的每一个顶点每一个顶点每一个顶点每一个顶点v v v vj j j j的最短有向路都求出来的最短有向路都求出来的最短有向路都求出来的最短有向路都求出来(或者指出不存或者指出不存或者指出不存或者指出不存在从在从在从在从v v v v1 1 1 1到到到到v v v vj j j j的有向路，即的有向路，即的有向路，即的有向路，即v v v v1 1 1 1不可达不可达不可达不可达v v v vj j j j)我们把整个计算分成若干我们把整个计算分成若干我们把整个计算分成若干我们把整个计算分成若干“轮轮轮轮”来进行来进行来进行来进行(一个一个一个一个“轮轮轮轮”就是一个大步就是一个大步就是一个大步就是一个大步)，每一轮中，将求出，每一轮中，将求出，每一轮中，将求出，每一轮中，将求出v v v v1 1 1 1到某一个顶到某一个顶到某一个顶到某一个顶点点点点v v v vj j j j的最短路以及这条最短路的长度的最短路以及这条最短路的长度的最短路以及这条最短路的长度的最短路以及这条最短路的长度b(j).b(j).b(j).b(j).我们把我们把我们把我们把b(j)b(j)b(j)b(j)就叫做顶点就叫做顶点就叫做顶点就叫做顶点v v v vj j j j的标号的标号的标号的标号.再强调一下，再强调一下，再强调一下，再强调一下，顶点顶点顶点顶点v v v vj j j j的标号的标号的标号的标号代表的是从代表的是从代表的是从代表的是从v v v v1 1 1 1到到到到v v v vj j j j的最短路的长度的最短路的长度的最短路的长度的最短路的长度.另外，如果说另外，如果说另外，如果说另外，如果说“顶顶顶顶点点点点v v v vj j j j已经有标号了已经有标号了已经有标号了已经有标号了”或或或或“v v v vj j j j是已标号点是已标号点是已标号点是已标号点”，就意味着，就意味着，就意味着，就意味着从从从从v v v v1 1 1 1到到到到v v v vj j j j的最短路以及这条最短路的长度都已经求出的最短路以及这条最短路的长度都已经求出的最短路以及这条最短路的长度都已经求出的最短路以及这条最短路的长度都已经求出来了来了来了来了.计算开始时，令计算开始时，令计算开始时，令计算开始时，令b(1)=0b(1)=0b(1)=0b(1)=0，v v v v1 1 1 1变为已标号点，其余变为已标号点，其余变为已标号点，其余变为已标号点，其余顶点都是未标号点顶点都是未标号点顶点都是未标号点顶点都是未标号点.这样做的意义很清楚，因为这样做的意义很清楚，因为这样做的意义很清楚，因为这样做的意义很清楚，因为b(1)b(1)b(1)b(1)代表从代表从代表从代表从v v v v1 1 1 1到到到到v v v v1 1 1 1的最短路的长度，当然不用计算就可以的最短路的长度，当然不用计算就可以的最短路的长度，当然不用计算就可以的最短路的长度，当然不用计算就可以知道，它应该等于知道，它应该等于知道，它应该等于知道，它应该等于0.0.0.0.如果计算是在一张图上进行，那么我们可以在顶如果计算是在一张图上进行，那么我们可以在顶如果计算是在一张图上进行，那么我们可以在顶如果计算是在一张图上进行，那么我们可以在顶点点点点v v v v1 1 1 1旁边写一个数旁边写一个数旁边写一个数旁边写一个数0 0 0 0，表示这是，表示这是，表示这是，表示这是v v v v1 1 1 1的标号并且已算出的标号并且已算出的标号并且已算出的标号并且已算出.每一轮计算可以分成下面几个步骤每一轮计算可以分成下面几个步骤每一轮计算可以分成下面几个步骤每一轮计算可以分成下面几个步骤.步骤步骤步骤步骤1 1 1 1 找出所具有下述性质的弧找出所具有下述性质的弧找出所具有下述性质的弧找出所具有下述性质的弧：起点：起点：起点：起点v v v vi i i i是已标号点而终点是已标号点而终点是已标号点而终点是已标号点而终点v v v vj j j j是未标号点是未标号点是未标号点是未标号点.如果这样的弧不存如果这样的弧不存如果这样的弧不存如果这样的弧不存在，计算结束在，计算结束在，计算结束在，计算结束.步骤步骤步骤步骤2 2 2 2 对于步骤对于步骤对于步骤对于步骤1 1 1 1中找到的每一条弧中找到的每一条弧中找到的每一条弧中找到的每一条弧，计，计，计，计算一个数：算一个数：算一个数：算一个数：k=b(i)+l.k=b(i)+l.k=b(i)+l.k=b(i)+l.(如果这个如果这个如果这个如果这个kkkk在前面各轮计算中已经算过，就在前面各轮计算中已经算过，就在前面各轮计算中已经算过，就在前面各轮计算中已经算过，就不必再算不必再算不必再算不必再算)也就是说：也就是说：也就是说：也就是说：kkkk等于弧的起点的等于弧的起点的等于弧的起点的等于弧的起点的 标号加标号加标号加标号加上弧的长度上弧的长度上弧的长度上弧的长度.把算出的把算出的把算出的把算出的kk的值就写在弧的值就写在弧的值就写在弧的值就写在弧的旁的旁的旁的旁边，并在数的外面加上一个方括号然后找出使边，并在数的外面加上一个方括号然后找出使边，并在数的外面加上一个方括号然后找出使边，并在数的外面加上一个方括号然后找出使kkkk最小的弧最小的弧最小的弧最小的弧(如果有好几条弧都使如果有好几条弧都使如果有好几条弧都使如果有好几条弧都使kkkk达达达达到最小，可任取一条到最小，可任取一条到最小，可任取一条到最小，可任取一条)步骤步骤步骤步骤3 3 3 3 把弧把弧把弧把弧画成粗线，把顶点画成粗线，把顶点画成粗线，把顶点画成粗线，把顶点v v v vd d d d变为已标变为已标变为已标变为已标号点，令号点，令号点，令号点，令v v v vd d d d的标号的标号的标号的标号b(d)b(d)b(d)b(d)就等于就等于就等于就等于k.k.k.k.这一轮计算结这一轮计算结这一轮计算结这一轮计算结束束束束.在一轮计算结束后，应该检查一下，是不是所有在一轮计算结束后，应该检查一下，是不是所有在一轮计算结束后，应该检查一下，是不是所有在一轮计算结束后，应该检查一下，是不是所有顶点都得到标号了，如果是的，那么整个计算就结束顶点都得到标号了，如果是的，那么整个计算就结束顶点都得到标号了，如果是的，那么整个计算就结束顶点都得到标号了，如果是的，那么整个计算就结束了；如果不是，即还有未标号的顶点，就转向下一轮了；如果不是，即还有未标号的顶点，就转向下一轮了；如果不是，即还有未标号的顶点，就转向下一轮了；如果不是，即还有未标号的顶点，就转向下一轮计算计算计算计算(即再从步骤即再从步骤即再从步骤即再从步骤1 1 1 1开始计算开始计算开始计算开始计算).).).).如果我们要求从如果我们要求从如果我们要求从如果我们要求从v v v vs s s s到到到到v v v vt t t t的最短路，只要的最短路，只要的最短路，只要的最短路，只要v v v vt t t t得到标号，得到标号，得到标号，得到标号，计算就结束了，从而可以省去一些计算计算就结束了，从而可以省去一些计算计算就结束了，从而可以省去一些计算计算就结束了，从而可以省去一些计算.如果在计算结束时，还有一些点没有得到标号，如果在计算结束时，还有一些点没有得到标号，如果在计算结束时，还有一些点没有得到标号，如果在计算结束时，还有一些点没有得到标号，那么可以肯定，从起点到这些点的有向路是不存在的那么可以肯定，从起点到这些点的有向路是不存在的那么可以肯定，从起点到这些点的有向路是不存在的那么可以肯定，从起点到这些点的有向路是不存在的.该计算方法的框式图如下：该计算方法的框式图如下：该计算方法的框式图如下：该计算方法的框式图如下：开始：令开始：令开始：令开始：令b(1)=0b(1)=0，v v1 1为已标号点为已标号点为已标号点为已标号点求所有起点已标号、终点未标号求所有起点已标号、终点未标号求所有起点已标号、终点未标号求所有起点已标号、终点未标号的弧的集合的弧的集合的弧的集合的弧的集合B B，B B是不是空集合？是不是空集合？是不是空集合？是不是空集合？对于对于对于对于B B中的每一条弧中的每一条弧中的每一条弧中的每一条弧，计算，计算，计算，计算，k=b(i)+l,k=b(i)+l,求出使求出使求出使求出使kk最最最最小的弧小的弧小的弧小的弧.将弧将弧将弧将弧加粗，令加粗，令加粗，令加粗，令b(d)=k,b(d)=k,v vd d成为已标号点成为已标号点成为已标号点成为已标号点是否还有未标号的顶点是否还有未标号的顶点是否还有未标号的顶点是否还有未标号的顶点计算结束计算结束计算结束计算结束是是是是否否否否是是是是 现在来讨论标号法好不好？要回答这个问题现在来讨论标号法好不好？要回答这个问题,首首先应该明确一下什么叫先应该明确一下什么叫“好好”,什么叫什么叫“不好不好”一一般说来，主要的好坏标准是计算起来快不快不快般说来，主要的好坏标准是计算起来快不快不快(还还有比的标准，例如容不容易拿上计算机计算；是否有比的标准，例如容不容易拿上计算机计算；是否易于普及等等易于普及等等)，或者说，用这个方法计算时，需要，或者说，用这个方法计算时，需要进行的运算次数多不多进行的运算次数多不多.当然，运算次数越少越好当然，运算次数越少越好.3.3 标号法好不好标号法好不好 大家也许会说，运算次数多少不完全决定于采大家也许会说，运算次数多少不完全决定于采用什么方法，还和要解决的问题有关同样用标号用什么方法，还和要解决的问题有关同样用标号法，解一个只有法，解一个只有10个顶点的问题可能只要进行几千个顶点的问题可能只要进行几千次运算，而解一个次运算，而解一个100个顶点的问题，就可能要进个顶点的问题，就可能要进行几百万次运算了，这又怎么比较呢？行几百万次运算了，这又怎么比较呢？办法还是有的办法还是有的.那就是，设图那就是，设图G有有n个顶点个顶点(为了为了简单起见，我们就不研究边数简单起见，我们就不研究边数m的影响了的影响了),我们来我们来估计一下，把标号法用到图估计一下，把标号法用到图G上去需要进行几次运上去需要进行几次运算算.当然，这样估计出来的结果不会是一个确定的当然，这样估计出来的结果不会是一个确定的数数,而是象而是象n2,3n3+4n2,2n等等这样的与等等这样的与n有关的数有关的数,即即n的函数的函数.然后再以这种函数为标准来比较方法的好然后再以这种函数为标准来比较方法的好坏坏.比如说，有两种方法，第一种要进行比如说，有两种方法，第一种要进行n3次加法，次加法，而第二种要进行而第二种要进行n5次加法，当然第一种就比第二种次加法，当然第一种就比第二种好，因为在好，因为在n较大时，较大时，n5比比n3要大多了要大多了.上面讲的是怎样比较两种方法谁好谁坏上面讲的是怎样比较两种方法谁好谁坏.现在总共只现在总共只讲了一个标号法，又怎么评论它的好坏呢？也有办法的讲了一个标号法，又怎么评论它的好坏呢？也有办法的.目前一般认为，如果一种方法所需要的运算次数能表目前一般认为，如果一种方法所需要的运算次数能表示成示成n的多项式，例如的多项式，例如n4,2n2+3n等等等等.这种方法就认为是这种方法就认为是好的，或者说是有效的好的，或者说是有效的.而如果一种方法的计算次数是而如果一种方法的计算次数是某一个数的某一个数的n次幂，例如次幂，例如2n,10n，即是，即是n的指数函数，这的指数函数，这种方法就认为是不好的，或者说是无效的种方法就认为是不好的，或者说是无效的.请看如下这请看如下这张表：张表：n5102030501001000方法A(运算次数n3)6251000800027000 625000106109方法B(运算次数2n)3210241061091015103010300上表中对一种需要进行上表中对一种需要进行n3次运算的方法次运算的方法A与另一种需要进与另一种需要进行行2n次运算的方法次运算的方法B进行了比较进行了比较(关于关于2n的近似值的近似值,我们是以我们是以210=1024103来估算的来估算的,例如例如250=(210)5(103)5=1015).从上表从上表可以看出，方法可以看出，方法B的运算次数的增长速度是惊人的的运算次数的增长速度是惊人的.也许有也许有的人会认为，现在反正有大型计算机，计算次数多一些无的人会认为，现在反正有大型计算机，计算次数多一些无所谓所谓.其实不然其实不然.例如我们有一个每秒能计算一百万次的计例如我们有一个每秒能计算一百万次的计算机，那么，在算机，那么，在1000秒内可以进行秒内可以进行10001000000=109次次(即十亿次即十亿次)运算运算,如果用方法如果用方法A,则则可以解决一个则则可以解决一个1000个顶个顶点的问题，而用方法点的问题，而用方法B呢？却只能解决一个呢？却只能解决一个30个顶点的问个顶点的问题题.如果想用方法如果想用方法B来解决一个来解决一个100个顶点的问题，即使用个顶点的问题，即使用的是每秒能计算一亿次的计算机，也需要的是每秒能计算一亿次的计算机，也需要1022秒，即要好秒，即要好几万亿年几万亿年.从上面的简单比较久可以看出，为什么说计算从上面的简单比较久可以看出，为什么说计算次数是次数是n的多项式的方法是有效的，而计算次数是的多项式的方法是有效的，而计算次数是n的指数函数的方法是无效的的指数函数的方法是无效的.另外，也可以看出，另外，也可以看出，单靠提高计算机的速度还不够，还必须从数学上寻单靠提高计算机的速度还不够，还必须从数学上寻求有效的计算方法求有效的计算方法.现在再回过头来看看标号法好不好现在再回过头来看看标号法好不好.回想一下标回想一下标号法的各轮计算，可以看出，它只包含两种运算：号法的各轮计算，可以看出，它只包含两种运算：加法与比较大小加法与比较大小(比较大小也需要花费时间，所以比较大小也需要花费时间，所以也要考虑也要考虑).加法用于计算加法用于计算k(i,j)，每计算一个，每计算一个k(i,j)进进行一次加法，而且每一条弧最多只计算一次行一次加法，而且每一条弧最多只计算一次.因此因此,如果图中有如果图中有m条弧，那么至多进行条弧，那么至多进行m次加法次加法.对于一对于一个有个有n个顶点的简单有向图来说，最多有个顶点的简单有向图来说，最多有n(n-1)条条弧弧(假设从每一个顶点假设从每一个顶点vi出发，都有出发，都有n-1条弧指向其条弧指向其他的他的n-1个顶点个顶点)，因此，最多进行，因此，最多进行n(n-1)次加法，次加法，放宽一点，也可以说，至多进行放宽一点，也可以说，至多进行n2次加法次加法.另外，在每一轮计算中，在找使另外，在每一轮计算中，在找使k(i,j)达到最小达到最小的弧的弧时，要用到比较大小的运算，一般说来，时，要用到比较大小的运算，一般说来，要从要从s个数中把最小的数找出来，要进行个数中把最小的数找出来，要进行s-1次比较次比较(例如有四个数例如有四个数a1,a2,a3,a4，那么可以先拿，那么可以先拿a1与与a2比，比，然后拿这两个数中小的数与然后拿这两个数中小的数与a3比，再拿小的数与比，再拿小的数与a4比，比三次就能知道哪个数最小了比，比三次就能知道哪个数最小了).那么在每一轮那么在每一轮的步骤的步骤1中，一般会选出几条弧呢？算得宽一些，中，一般会选出几条弧呢？算得宽一些，至多至多n2条吧条吧(事实上要少得多事实上要少得多)，因此至多进行，因此至多进行n2次次比较，整个计算的轮数不会超过比较，整个计算的轮数不会超过n，因此，总起来，因此，总起来说，至多进行说，至多进行n3次比较大小的运算次比较大小的运算.通过上面的估计，可以得出这样的结论：把标通过上面的估计，可以得出这样的结论：把标号法用在一个号法用在一个n个顶点的图上，至多进行个顶点的图上，至多进行n2次加法次加法和和n3次比较大小次比较大小.因此，可以说，标号法是一种好的、因此，可以说，标号法是一种好的、有效的计算方法有效的计算方法.问题：问题：给定简单权图给定简单权图G=(V,E)，并设，并设G 有有n个顶点，个顶点，求求G中点中点u0到其它各点的最短路到其它各点的最短路.Dijkstra算法算法 (Edmonds,1965)(2)若若i=n-1，则停；否则令，则停；否则令 =V Si,对每个对每个v ，令，令 l(v)=min l(v)，l(ui)+w(uiv)(1)置置 l(u0)=0；对所有；对所有vV u0，令，令 l(v)=；S0=u0，i=0.3.4 求无向图上的最短路的方法求无向图上的最短路的方法并用并用 ui+1记达到最小值的某点记达到最小值的某点.置置S i+1=Siu i+1，i=i+1（表示赋值语句，以后的算法中相同），转（表示赋值语句，以后的算法中相同），转（2）.终止后，终止后，u0 到到 v 的距离由的距离由 l(v)的终值给出的终值给出.)(minvliSv(3)计算计算说明：说明：（1）算法中算法中w(uiv)表示边表示边 uiv 的权；的权；（2）若只想确定若只想确定u0到某顶点到某顶点v0的距离，的距离，则当某则当某 uj 等于等于 v0 时即停；时即停；（3 3）算法稍加改进可同时得出算法稍加改进可同时得出u u0 0到其它点的最短路到其它点的最短路.例例3 求图求图 G 中中 u0 到其它点的距离到其它点的距离.u0 742155813G:解解 u0 742155813 （a）初始标号）初始标号u0 742155813 2 4 7（b）用与）用与u0关联的边的关联的边的权权2,4,7分别更新与分别更新与u0相邻相邻的三个点的标号的三个点的标号;（c）取小圆点中）取小圆点中标号最小者得标号最小者得 u1；u0 742155813 2 4 7u1（d）对与对与u1相邻的小圆点，相邻的小圆点，用用 l(u1)+w(u1v)=2+1=3更新标号更新标号4；2+5=7 更新两个更新两个；u0 742155813 2 7 37 7u1（e）取小圆点中标号）取小圆点中标号 最小者得最小者得 u2.u0 742155813 2 7 37 7u1 u2 u4 u0 742155813 2 7 34 6（h）u1 u2 0u3u5 u0 742155813 2 7 37 7u1 u2 4（f）u0 742155813 2 7 3 6u1 u2（g）u0 742155813 2 7 34 6u1 u2 u33.5 图的距离表图的距离表 在生产实践中，往往需要求出一个图的任意两个顶点在生产实践中，往往需要求出一个图的任意两个顶点在生产实践中，往往需要求出一个图的任意两个顶点在生产实践中，往往需要求出一个图的任意两个顶点之间的最短路之间的最短路之间的最短路之间的最短路.例如，一个铁路局在编制他所属的各个车例如，一个铁路局在编制他所属的各个车例如，一个铁路局在编制他所属的各个车例如，一个铁路局在编制他所属的各个车站之间的运输里程表时，就会遇到这类问题另外，对于站之间的运输里程表时，就会遇到这类问题另外，对于站之间的运输里程表时，就会遇到这类问题另外，对于站之间的运输里程表时，就会遇到这类问题另外，对于不少图论中的极值问题，往往在计算前首先必须把图中任不少图论中的极值问题，往往在计算前首先必须把图中任不少图论中的极值问题，往往在计算前首先必须把图中任不少图论中的极值问题，往往在计算前首先必须把图中任意两个顶点之间的最短路及最短路的长度都求出来意两个顶点之间的最短路及最短路的长度都求出来意两个顶点之间的最短路及最短路的长度都求