§3 设备更新与中心选址一、指定顶点对之间的最短路径算法对图G 每一条边i e 都规定一个正实数)(i e a 与之对应，所得到的图称为赋权图，称)(i e a 为边i e 的权。
边),(j i v v 上的权记成),(j i v v a 。
对赋权图G ，s ∀，V t ∈，G 中的),(t s 一路称为最短路，如果它的各边的权和是G 中任一条),(t s 一路中各边权和最小的。
找寻),(t s 最短路最有效的算法是Dijkstra 算法：其主要思路是假定我们已经知道了在图中与起点s 有最短路径的m 个顶点以及从s 到这些顶点间的最短路径，然后求出第1+m 个顶点使之与前m 个顶点有相同的属性。
其实现方法是比较法。
对于每一个未着色的顶点y ，考虑所有已着色的顶点x ，从1s 通过已着色的顶点到y 的不同路径中选出它们中的最短路径，从而也就确定了新染色的点和相应的最短路径，不断重复上述过程直至求得从s 到t 的最短路径为止。
算法步骤如下：1、最初，所有的边和顶点均未着色，对每一顶点x 指定一个数)(x d ，表示从s 到x 且仅使用已着色顶点作为中间顶点的最短路径长度。
2、令0)(=s d ，并对所有s x ≠，有∞=)(x d ，对顶点s 着色并令s y =。
3、对于每一个未着色顶点x ，重新定义)(x d 如下： {}),()(),(min )(x y a y d x d x d +=如果对于所有未着色的顶点x ，∞=)(x d ，则算法停止，因为此时从s 到任一未着色的顶点都没有路，也就不存在从s 到t 的路径。
否则找出一个具有最小的)(x d 值的顶点，对其着色并令x y =。
4、重复步骤3直到顶点t 已经着色时为止，算法终止。
从s 到t 的最短路径已求出。
例：用Dijkdtra 算法求下图中从顶点s 到t 的最短路径。
a 34 b 2 7s 8 2 3 t3c 3d 21、对s 着色，令0)(=s d ，且对其余顶点均有∞=)(x d ，)(s x ≠.2、令s y =，对所有x 求解：{}4),()(),(min )(=+=a s a s d a d a d {}7),()(),(min )(=+=b s a s d b d b d {}3),()(),(min )(=+=c s a s d c d c d {}8),()(),(min )(=+=d s a s d d d d d {}∞=+=),()(),(min )(t s a s d t d t d由于3)(=c d 最小，再对c 着色，并对边),(c s 着色。
