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
1701010045
1701010046
1701010047
1701010048
（2），则有：
1701010049
1701010050
1701010051
1701010052
1701010053
1701010054
（3）修正，则有公式：
1701010055
1701010056
1701010057
1701010058
1701010059
继续转（2），即按照下面的循环计算。
1701010060
1701010061
1701010062
（4），则有：
1701010063
1701010064
1701010065
1701010066
1701010067
1701010068
（5）修正，则有公式：
1701010069
1701010070
1701010071
1701010072
1701010073
编写dijkstra（）函数如下：
1701010074