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
【分析】
1701010033
1701010034
根据图8-22写出图G的带权邻接矩阵：
1701010035
1701010036
1701010037
1701010038
1701010039
则相应的权值wij即是W的第i行第j列的元素。由于G是无向图，可见W为对称阵。
1701010040
1701010041
1701010042
（1）令，则有：
1701010043
1701010044
