信息系统项目管理师综合知识真题考点：图与网络分析-最短路径问题

温馨提示：该考点请多结合试题进行理解。

最短路径问题常用Dijkstra标号法进行求解，该方法可用于求解指定两点vs,vt间的最短路，或从指定点vs到其余各点的最短路，目前被认为是求无负权网络最短路问题的最好方法。

算法的基本思路：若序列{vs，v1，...vn-1,vn}是从vs到vn的最短路，则序列{vs，v1，...vn-1}必为从vs到vn-1的最短路。

算法描述：

1、初始时，P只包含起点v1;T包含除v1外的其他顶点，且T中顶点的距离li为起点v1到该顶点的距离。

2、从T中选出距离起点v1最短的顶点k，并将顶点k加入到P中;同时，从T中移除顶点k。

3、 更新T中各个顶点到起点v1的距离。之所以更新T中各顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k作为跳板来更新其它顶点的距离。例如，T中有一点s和k相邻，s到起点v1的距离可能大于k到v1的距离+k到s的距离。

4、重复步骤2和3，直到遍历完所有顶点。

考点相关真题