软件水平考试

【单选题】11个乡镇之间的光缆铺设网络结构及每条光缆长度如图3-7所示。从乡镇s到乡镇t的最短光缆铺设距离为 (66) 公里。

A．92
B．82
C．81
D．73
网考网参考答案：C
网考网解析：
[要点解析] 本试题第一问关于图论算法中两节点间最短距离求解的问题，也可看做赋权简单连通无向图的单源问题的求解。求单源最短距离主要使用迪克斯特拉(E.W.Dijkstra)算法求解，即按路径长度递增顺序产生各节点最短距离。 对于图3-7，从乡镇s到乡镇t的最短距离为21+20+20+8+12=81公里。 查看试题解析出处>>