如下图所示,每个结点代表工厂的一个车间,线上的数字为两结点间的距离(单位为米),如何铺设暖气管道,才能使管道总长最小。

admin2017-01-21  30

问题 如下图所示,每个结点代表工厂的一个车间,线上的数字为两结点间的距离(单位为米),如何铺设暖气管道,才能使管道总长最小。

选项

答案从终点逆向标到起点即可,从6开始标,和6相连的有1,5,4分别为150,32,20,5到6只有一条路线为32,4到6有两条,4到5到6为25+32=57,4到6为20,那么和6相连的选择4,再从4出发,和4相连的有3和5,分别为35,25,且都只有一条,那么3→4→6为35+20=55,5→4→6为25+20=45,选择5和4相连,这样一直往前推进,选择最小的即可。如下图所示: [*] 说明:方框中的数字代表改点到终点最短距离;方框上的标示从改点到终点最短路线的走法。

解析
转载请注明原文地址:https://kaotiyun.com/show/2Vjx777K
0

最新回复(0)