最短路径算法dijkstra

该算法的核心就是从当前节点的邻居节点中找到距离起始节点的最近那个节点，作为下步迭代的节点。

一 算法步骤

1. 给定起始节点$s(v_0)$s(v0​)、邻接矩阵$A$A；
2. 初始化$n$n维零标记向量$label$label，$n$n维$inf$inf距离向量$distance$distance；
3. $s(v_0)$s(v0​)开始，更新$label[0] = 1$label[0]=1，$distance[0] = 1$distance[0]=1；
4. 遍历搜索，更新$label$label、$distance$distance，记当前搜索节点$v_i$vi​，如果$label[j] != 1且A[i,j] + distance[i] < distince[j]$label[j]!=1且A[i,j]+distance[i]<distince[j],更新$distince[j] = A[i,j] + distance[i]$distince[j]=A[i,j]+distance[i]，$j 为 min(A[i,j] + distance[i])$j为min(A[i,j]+distance[i])时的下次搜索节点，更新$label[j] = 1$label[j]=1。

二 例子

1. 邻接矩阵A

2. 示例图
   
3. 过程

3.1 $v_0$v0​，$A$A;
3.2 标记向量$label = [0, 0, 0, 0, 0, 0]$label=[0,0,0,0,0,0]、
距离向量$distance = [inf, inf, inf, inf, inf, inf]$distance=[inf,inf,inf,inf,inf,inf]；
3.3 $v_0$v0​开始，所以更新
$label = [1, 0, 0, 0, 0, 0]$label=[1,0,0,0,0,0]，
$distance = [0, inf, inf, inf, inf, inf]$distance=[0,inf,inf,inf,inf,inf]；
3.4 更新$label、distance$label、distance
因为$label[1] != 1且A[0,1] + distance[0] < distince[1]$label[1]!=1且A[0,1]+distance[0]<distince[1]，所以更新$distince[1] = 1$distince[1]=1，
因为$label[1] != 1且A[0,2] + distance[0] < distince[2]$label[1]!=1且A[0,2]+distance[0]<distince[2]，所以更新$distince[2] = 12$distince[2]=12，
$1 为 min(A[i,j] + distance[i])$1为min(A[i,j]+distance[i])时的下次搜索节点$v_1$v1​，
此时
$label = [1, 1, 0, 0, 0, 0]$label=[1,1,0,0,0,0]
$distance = [0, 1, 12, inf, inf, inf]$distance=[0,1,12,inf,inf,inf]
最终得到$distance = [0, 1, 8,4,13, 17]$distance=[0,1,8,4,13,17]。