Dijkstra最短路径算法

Dijkstra最短路径算法

求单源到其他所有节点的最短路径，时间复杂度o( n^2 )

算法特点：

每次找出前一次迭代后具有最低费用的节点，添加到集合中；

第k次迭代后，可以知道到k个目的节点的最低费用路径；

伪代码：

Initialize:
N'={u}
for all nodes v
   if v is a neighbor of u
   	   then D(v) =C(u,v)
   else D(v)=∞

Loop
   find w not in N' such that D(w) is a minimum
   add w to N'
   update D(v) for each neighbor v of w and not in N'
          D(v) =min (D(v), D(w)+C(w,v))
   /** new cost to v is either old cost to v or known
   least path cost to w plus cost from w to v
   */
Until N'=N

以下是一个实例(出现在计算机网络的路由选择问题中):

以下表格展示了算法的执行过程：

D(v) 表示从源节点到v的路径大小，
P(v)表示从源节点到v的最短路径的前一节点

Dijkstra算法在计算机网络的路由选择算法中有应用