中国邮递员问题的求解实例前面已经讲过，对于欧拉图，可以直接用Fleury算法找出一条欧拉巡回路线；对于半欧拉图，可以先求出奇点u和v之间的最短路径P，令，则G*为欧拉图，然后用Fleury算法来确定一个G*的欧拉巡回，它就是G的最优巡回。当G有2n个奇点（n>1），可以用Edmonds算法解决，步骤如下：(1)用Floyd算法求出所有奇点之间的最短路径和距离矩阵。(2)用匈牙利法或0-1规划法求出所有奇点之间的最佳配对。(3)在原图上添加最佳配对所包含的两两顶点之间的最短路得到欧拉图G*。(4)用Fleury算法确定一个G*的欧拉巡回，这就是G的最优巡回。以上步骤的关键是找出2n个奇点的最佳配对，举例如下。例图3是某区街道示意图，各边的长度数据如下表所示。现在需要对每条街道都巡视到（至少走一次），求一条总路程最短的巡回路线。序号顶点顶点边长序号顶点顶点边长序号顶点顶点边长序号顶点顶点边长1121026171117163332324432493031342214402188928934232819850313264832310261981524535232210851313625342739820923396362221414523332486531145021121330637254281053333825264121812212182723825241095432372357452542313191993924291845535361808109289241617199402132432563540180910112352517252354127263265736376481010161632615143604227313065837384681156414271522217432630271593741184125131482814212194428294146042411063136203822919203444528332356140417921467253301918332462934181624039198157825231182614447343341816714219322021308483039432解：该图有42个顶点和62条边，有26个顶点为奇点，因而不是欧拉图，为了寻找最优巡回，需要先求26个奇点的最佳配对。先用Floyd算法求出所有42个顶点之间的最短路距离和路径。程序如下：E=[12102614402……………注：每一行代表一条边（两个顶点和边长），此处省略59行4039198];---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---fori=1:42forj=1:42ifj==ia(i,j)=0;elsea(i,j)=inf;endendendfork=1:62i=E(k,1);j=E(k,2);a(i,j)=E(k,3);a(j,i)=E(k,3);end[D,R]=floyd(a);然后求26个奇点的最优配对，这可以用Lingo求解，编写程序如下：---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---图3某区街道示意图123456798101112131415161718192021222324252627282930313233343536373839404142MODEL:SETS:dot/2,4,5,6,8,9,10,11,12,13,14,15,17,18,19,20,22,24,25,26,28,29,30,36,40,41/;LINKS(dot,dot)|2#GT#1:C,X;ENDSETSDATA:C=1319106565165093912281463150012136178951590170913771033111216521761185314181832212421512479168725466811731462175119818140211401418211345360194516352175228459719412355868146314982104414919120814971732435148886116418596793476911381192120308231687210110941689172418505057941083131884956247275014451058726382967150716161202127316871473200521031541289578813135410674712459401563123188746210021111170776811821978200523331541289524164313567605346511852152011765048288861996594100822672197252517332351932164510498233622141180914657937065972285883890255624862814202221671880128410581632376204417001028507398252011056912766265829862194306132115992294272505849157121112220416187722916871282131720081034131220075311995431265180519146751571198594615411576170236014111203871527577111712261347883129716181534186210701101156312318872177578661707523937197818942222143022821950160688434423524269425282603249528232031332676139819382047144170421184151010104518243441066160617154761372178674713421377150372212621371820102814421091162317211159540649154230672018131729205712651092082598184225921512479168721917072932368226025881796184822622718669011680414171116031931113920751967229515035956301409360832792;ENDDATA---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---图426个...