black

运筹学

登录

填空题

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

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

【参考答案】

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

相关考题

名词解释 整数变量

问答题 根据所给的表和一组解判断是否最优解,若不是,请求出最优解。

判断题 含n个顶点的树不一定只有n-1条边。

All Rights Reserved 版权所有©PP题库网库(pptiku.com)

备案号:湘ICP备14005140号-5

经营许可证号:湘B2-20140064