最短路线（二）<练习题>

　　1．某市有若干个风景点，如图14—9中a、b、c、d、e、…、i、j．一游客想一天游遍所有的景点，他从旅馆出发，最后再返回旅馆，他怎么走才能使所走的路线最短，全程多少千米（图中标的数字表示道路的千米数）？

　　2．图14—10是一个城市道路图，数字表示各段路的路程（单位：千米），求出图中从a到e的最短路线．

　　3．某工厂要为它下面的六个车间安装质量监测仪表，并把它们与工厂总监测中心连起来，如图14—11，请你为此图设计一条线路，使得所用电线最短（单位：米）．

　　4．如图14—12中，若a点地势最高，依次为a、b、c、d、e、f、g、h（h为最低点），在a点放水，求出水能流到每一点的最短通道（单位：米）．

　　5．街道旁有五栋居民楼a、b、c、d、e，如图14—13，现要立一个邮筒，为使五栋楼的居民到邮筒的距离之和最短，邮筒应立在何处？

　　答案仅供参考：

　　1．根据图14-9知，奇点为b、c、e、f、h、i、k、j这八个点，将这八个奇点按图14-1’的虚线所示连接，这八个奇点变为偶点．

　　且最短路线为：旅馆→a→b→c→b→i→h→g→f→e→d→c→k→j→f→e→k→j→h→i→旅馆．

　　全路程长为：

　　3×4＋1.5×2＋5×2＋2.5×2＋1×2=32（千米）．

　　2．从ahgfe这条路走，它的长度是：5+4＋2+7=18（千米）；从ahife这条路走，它的长度是：5+3＋1＋7=16（千米）；其它路线都比它们长，所以从a→h→i→f→e是最短路线，它的长度是16千米．

　　3．用剪圈法，在bfeb中剪去be，在bfgcb中剪去bc，在cgdc中剪去cd，在egde中剪去ed，在efge中剪去eg，ab是连接中心的唯一一条路线必须保留，最后将原题转化成了树形网络图，如图14-2’，且它的总长度最短．

　　使用电线长为：

　　2×（20＋10＋8＋40+16＋20）=228（米）

　　4．用取短法，从h点考虑，有两条通道gh、dh，gh最短，留gh；同理g点有两条通道cg、fg，留cg；f点只有bf一条通道，e点有最短通道de，d点的最短通道是cd，c点的最短通道是bc，b点只有ab这一条通道，所以得到水能流到每一点的最短通道，如图14-3’所示．

　　最短通道的长为：

　　12+18+5+8＋3＋12＋4=62（米）．

　　5．将五栋楼看成五个点，由于点的个数是奇数，所以要使五栋楼的居民到邮筒的距离之和最短，邮筒应设在c点．