问答题
{{B}}最短路问题{{/B}}
有一配送中心向某一客户送货，其行车可能途径6个地点，为简便描述，我们假定该配送中心位置在1处，客户在8处，其他6个地点依次为2、3、4、5、6、7处，各点之间的交通线路如图6，其中箭头上的数字代表了两地间的距离(km)，求配送中心到客户的最短距离和行车路线。
【正确答案】
【答案解析】解：这是一个典型的最短路问题，该问题的解法可以用Dijkstra方法，Dijkstra方法的基本思想是从交通图中某点(vs)出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为P标号)、或者是从vs到该点的最短路的权的上界(称为P标号)，方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，这样，经过有限的步骤，就可以求出从vs到各点的最短路。
第一步：
min {c12，c14，c16}=min{0+2，0+1，0+3}=min{2，1，3}=1；X={1，4}， w4=1
第二步：
min {c12，c16，c42，c47}=min {0+2，0+3，1+10，1+2}=min {2，3，11，3} =2;X= {1，2，4}，w2=2
第三步：
min {c16，c23，c25，c47} =min {0+3，2+6，2+5，1+2} =min {3，8，7，3} =3； X= {1，2，4，6}，w6=3
第四步：
min {c23，c25，c47，c67} =min {2+6，2+5，1+2，3+4} =min {8，7，3，7} =3； X= {1，2，4，6，7}，w7=3
第五步：
min {c23，c25，c75，c78} =min {2+6，2+5，3+3，3+8} =min {8，7，6，11} =6； X= {1，2，4，5，6，7}，w5=6
第六步：
min {c23，c53，c58，c78} =min {2+6，6+9，6+4，3+8} =min {8，15，10，11} =8;X= {1，2，3，4，5，6，7}， w3=8
第七步：
min {c38，c58，c78} =min {8+6，6+4，3+7} =min {14，10，11} =10；X= {1， 2，3，4，5，6，7，8}， w8=10
第八步：
1到10的最短路径为{1，4，7，5，8}，长度为10。
行车路线见图25。
第一步：
min {c12，c14，c16}=min{0+2，0+1，0+3}=min{2，1，3}=1；X={1，4}， w4=1
第二步：
min {c12，c16，c42，c47}=min {0+2，0+3，1+10，1+2}=min {2，3，11，3} =2;X= {1，2，4}，w2=2
第三步：
min {c16，c23，c25，c47} =min {0+3，2+6，2+5，1+2} =min {3，8，7，3} =3； X= {1，2，4，6}，w6=3
第四步：
min {c23，c25，c47，c67} =min {2+6，2+5，1+2，3+4} =min {8，7，3，7} =3； X= {1，2，4，6，7}，w7=3
第五步：
min {c23，c25，c75，c78} =min {2+6，2+5，3+3，3+8} =min {8，7，6，11} =6； X= {1，2，4，5，6，7}，w5=6
第六步：
min {c23，c53，c58，c78} =min {2+6，6+9，6+4，3+8} =min {8，15，10，11} =8;X= {1，2，3，4，5，6，7}， w3=8
第七步：
min {c38，c58，c78} =min {8+6，6+4，3+7} =min {14，10，11} =10；X= {1， 2，3，4，5，6，7，8}， w8=10
第八步：
1到10的最短路径为{1，4，7，5，8}，长度为10。
行车路线见图25。