填空题

某电信计划在甲、乙两地铺设通信电缆,如图是甲、乙两地间的交通图,v1表示甲地,v6表示乙地,点之间的连线(边)表示两地公路,边上的数值表示两地间公路的长度(单位:千米)。如何铺设才能使甲、乙两地的电缆长度最短。

Dijkstra标号法:
(1)开始先给始点vs标(),其余为临时标号为∞;
(2)从刚确定的固定标号点,修改与其关联的所有临时标号点的值,取代∞;
(3)在所有临时标号点中选取最小者,将其改为固定标号;
(4)返回2重复至所有点均为固定标号。
经求解最短路是(),最短距离是(),所以应在()、()间铺设线路。

【参考答案】

0;V1-V2-V6;19;V1-V2;V2-V6