1701009970
1701009971
由此可得到最小树模型如图8-21所示。
1701009972
1701009973
1701009974
1701009975
1701009976
图8-21 最小树模型
1701009977
1701009978
最小树应用比较广泛，在电网、互联网结构及石油管道中，为了保证连接所有节点所使用材料最少，即可用最小树模型，这样求解的结果能够实现最优化求解。因此最小树模型应用是数学理论结合实际应用的典型代表。
1701009979
1701009980
1701009981
1701009982
1701009983
我和数学有约：趣味数学及算法解析 [:1701004266]
1701009984
我和数学有约：趣味数学及算法解析 8.6 最短路问题
1701009985
1701009986
【问题】何谓最短路？
1701009987
1701009988
【分析】
1701009989
1701009990
最短路问题（short-path problem）：若网络中的每条边都有一个数值（长度、成本和时间等），则找出两节点（通常是源节点和目标节点）之间总权和最小的路径就是最短路问题。
1701009991
1701009992
最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。
1701009993
1701009994
1701009995
1701009996
1701009997
1701009998
首先假设图的表述为：G=（V，E，W），其中顶点集，即顶点的个数｜V｜=p。wij表示边（vi，vj）的权，且需要满足非负条件。如果，则令。最短路问题即为求G中v1到其他各顶点的最短路径。用d（vj）表示从v1到vj的只允许经过已选出顶点的最短路径的权值。
1701009999
1701010000
相应的Dijkstra算法算法步骤如下。
1701010001
1701010002
1701010003
1701010004
1701010005
（1）初始化，令，；
1701010006
1701010007
（2）在R中寻找一个顶点vk，使得：
1701010008
1701010009
1701010010
1701010011
1701010012
1701010013
1701010014
置。若，则算法终止，否则转（3）；
1701010015
1701010016
1701010017
（3）修正d（vj），对R中每个vj，令：转（2）。
1701010018
1701010019
