第三章 最短路问题,让我们先把最短路问题的提法明确一下,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 渡河问题：一个人带了一只狼、一只羊和一棵白菜想要过河,河上有一只独木船,每次除了人以外,只能带一样东西.另外,如果人不在旁时,狼就要吃羊,羊就要吃白菜.问应该怎样安排渡河,才能
