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
1701010020
1701010021
这个算法经过｜V｜-1次循环之后，所有顶点都被选出，的终值就给出了从顶点v1到其余各顶点的最短路径的长度，反向追踪即可以得到最短路径。
1701010022
1701010023
【问题】
1701010024
1701010025
假设有一个旅行家，他居住在城市v1，他计划游览附近的若干城市，假设这些城市网络可以用图8-22来表示，现在他首先要估算从A出发到城市v8的最少花费，然后确定行程，如何求解v1到各顶点的最短距离。
1701010026
1701010027
1701010028
1701010029
1701010030
图8-22 城市网络图
1701010031
1701010032
【分析】