已知连接5个城市的高速道路设计图如题图所示 , 图中线边的数字表示拟建高速道路的费用(单位 : 百亿元) , 现在要在这5个城市间建设高速道路 , 要求高速道路的总费用最少 ,试画出建设方案并求最少的高速道路的总费用。
【正确答案】：
取一点V1，找出与V1最近的未接点V2，将V2与V1连上；
再找出与V1，V2最近的未接点，是V5，将V2与V5连上；
再找出与V1、V2、V5最近的未接点，是V4，将V4与V5连上；
最后找出与V1、V2、V4、V5最近的未接点，是V3，将V3与V2连上。
最少的高速道路的总费用为9（百亿元）。
【题目解析】：
最小枝杈树算法是按把最近的未接点连接到那些已接点上去的方法来进行的。
据此原理可找出高铁铁路的总长度最小的方案。
最少的高速道路的总费用为3+3+2+1=9（百亿元）。