数据结构与算法：Dijkstra最短路径算法

Dijkstra算法被应用于图中求解最短路径问题，在路径选择过程中同样发挥了重要作用。考虑一个具体的图示：

算法执行过程：

1. 定义一个起始节点，并将所有其他节点设置为从该起始节点出发的成本表格D及其上一个节点（即初始时就是起点）。
2. 从成本表格D中找出最小的成本值，并选择对应的那个节点作为下一个目标p；然后对尚未被访问过的所有其他目标n进行成本计算：新的成本= min(D(n), D(p) + 边权重(p→n))。
   具体而言，

D(n)=min(D(n),D( p)+c(p,n))

并记录该最小值所指向前一个节点；当且仅当当前开销表中的数值D(p)是最小值时，则选择该节点（在首次循环中指向初始点）。

PS：c ( n , p )记为p点到当前点n的开销路径值。

3、循环第二步，直到遍历完所有的节点。

以上图为例一步步阐述算法执行的过程。

1、首先选择u作为起点，其他各个点到u的开销表为：

已加入节点	D(x)	D(v)	D(w)	D(y)	D(z)
u	1,u	2,u	5,u	∞	∞