Dijkstra(迪杰斯特拉)算法是

典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径

无向图为以下（对称） ：

 

算法本质：

第一个最短点

（直接与0.源点连接）

第二个次短点

（要么直接与0.源点连接，要么经过1.最短点）

第三个次短点

（要么直接与0.源点连接，要么经过1.第一最短点，要么经过2.第二次短点）

迪杰斯特拉算法总共就干了两件事：

【1】不断运行广度优先算法找可见点，计算并更新可见点到源点的最短距离长度：

disp[]数组表示起点到该点的最短距离： 

次短点连接的边+起点到次短点的距离  与  次短点到起点的最短距离

 

【2】

从当前已知的路径disp[]数组中（排除之前确定下的更小的点）中

选择距离最短的路将其顶点继续搜索

 

 【3】排除此时距离最短的顶点（不再进行找次短点的比较）

 

以上循环：

【4】直至disp[]所有都遍历完（不再有可见点）

 

变式：

 

 

 题眼：将多起点改为单起点，多终点改为单终点

（即可转化为迪杰斯特拉算法）

 找到次短点为其中一个终点，即结束