某一个配送中心要给一个快餐店送快餐原料，应按照什么路线送货才能使送货时间最短。下图给出了配送中心到快餐店的交通图，图中V1，……

某一个配送中心要给一个快餐店送快餐原料，应按照什么路线送货才能使送货时间最短。下图给出了配送中心到快餐店的交通图，图中V₁，……，V₇表示7个地名，其中V₁表示配送中心，V₇表示快餐店，点之间的联线表示两地之间的道路，边所赋的权数表示开车送原料通过这段道路所需要的时间（单位：分钟）

【正确答案】：解：①给起始点V₁标号为（0，S）
②I={V₁},J={ V₂，V₃，V₄，V₅，V₆ ,V₇} ，边的集合{[V_I，V_J] ︳V_I，V_J两点中一点属于I,而另一点属于J}={[ V₁，V₂]，[ V₁，V₃]}，并有S₁₂=L₁+C₁₂=0+4=4；S₁₃=L₁+C₁₃=0+18=18，MIN (S₁₂,S₁₃)= S₁₂ =4
给边[ V₁，V₂]中的未标号的点V₂ 标以（4，1），表示从V₁ 到V₂ 的距离为4，并且在V₁到V₂的最短路径上V₂的前面的点为V₁.
③这时I={V₁ ，V₂},J={V₃，V₄，V₅，V₆ ,V₇}，边的集合{[V_I，V_J] ︳V_I，V_J两点中一点属于I,而另一点属于J}={[ V₁，V₃]，[ V₂，V₃]，[ V₂，V₄]}，并有S₂₃=L₂+C₂₃=4+12=16 ；S₂₄=L₂+C₂₄=4+16=20 ；MIN (S₂₃,S₂₄ , S₁₃)= S₂₃ =16
给边[ V₂，V₃]中的未标号的点V₃ 标以（16，2）
④这时I={V₁ ，V₂ ，V₃},J={V₄，V₅，V₆ ,V₇}，边的集合{[V_I，V_J] ︳V_I，V_J两点中一点属于I,而另一点属于J}={[ V₂，V₄]，[ V₃，V₄]，[ V₃，V₅]}，并有S₃₄=L₃+C₃₄=16+2=18 ； S₃₅=L₃+C₃₅=16+6=22 ； S₂₄=L₂+C₂₄=4+16=20MIN (S₃₄,S₃₅,S₂₄)= S₃₄ =18
给边[ V₃，V₄]中的未标号的点V₄ 标以（18，3）
⑤这时I={V₁ ，V₂ ，V₃ ，V₄},J={V₅，V₆ ,V₇}，边的集合{[V_I，V_J] ︳V_I，V_J两点中一点属于I,而另一点属于J}={ [ V₄，V₆]，[ V₄，V₅]，[ V₃，V₅]}，并有S₄₆=L₄+C₄₆=18+7=25 ； S₄₅=L₄+C₄₅=18+8=26 ；MIN (S₄₆,S₄₅ ,S₃₅)= S₃₅ =24
给边[ V₃，V₅]中的未标号的点V₅ 标以（24，3）
⑥这时I={V₁ ，V₂ ，V₃ ，V₄ ，V₅ },J={ V₆ ，V₇}，边的集合{[V_I，V_J] ︳V_I，V_J两点中一点属于I,而另一点属于J}={[ V₅，V₇]，[ V₄，V₆] }，并有S₅₇=L₅+C₅₇=22+5=27 ；MIN (S₅₇,S₄₆)= S₄₆ =25给边[ V₄，V₆]中的未标号的点V₆ 标以（25，4）
⑦这时I={V₁ ，V₂ ，V₃ ，V₄ ，V₅ ，V₆ },J={ V₇}，边的集合{[V_I，V_J] ︳V_I，V_J两点中一点属于I,而另一点属于J}={[ V₅，V₇]，[ V₆，V₇] }，并有S₆₇=L₆+C67=25+6=31 ；MIN (S₅₇,S₆₇)= S₅₇ =27
给边[ V₅，V₇]中的未标号的点V₇ 标以（27，5）
⑧此时I={V₁ ，V₂ ，V₃ ，V₄ ，V₅ ，V₆ ，V₇},J=空集，边集合{[V_I，V_J] ︳V_I，V_J两点中一点属于I,而另一点属于J}=空集，计算结束。
⑨得到最短路。从V₇ 的标号可知从V₁ 到V₇ 的最短时间为27分钟。
即：配送路线为： V₁ →V₂ →V₃ →V₅ →V₇