最短路径的寻求问题

小学教育网

　　下面是城市公园的地图，图中所列数字以m为单位。每天早上公园开门前，清洁工人必须开着清洁车打扫公园内所有的街道。该清洁车位于H点。令清洁工人感到很困扰的是，欲清扫完公园内所有的街道，似乎不可能不走重复的路段。这种情形真的无法避免吗？
　　你能说出清洁车清扫完所有路段再回到H点的最短路径吗？
　


解答与分析
　　清洁工人不可能清扫完所有的路径而没有任何一条路段重复。最短的路径是 1560 m(其中 1330 m是清扫路径， 230 m是重复经过的路径)，欲走完所有路径必须重复经过AB、HG及IF。下面为最短路径的一个例子：
H B C D H I D E F I F G H G A B A H
　　本题的数学分析基础在于该路径所形成的网路中奇结点和偶结点的分布情况。