基本思想
dijkstra的算法思想是从以上最短距离数组中每次选择一个最近的点，将其作为下一个点，然后重新计算从起始点经过该点到其他所有点的距离，更新最短距离数据。已经选取过的点就是确定了最短路径的点，不再参与下一次计算。
- 通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。
- 此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
- 初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 … 重复该操作，直到遍历完所有顶点。
操作步骤
- 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为”起点s到该顶点的距离”[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。
- 从U中选出”距离最短的顶点k”，并将顶点k加入到S中；同时，从U中移除顶点k。
- 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。
- 重复步骤(2)和(3)，直到遍历完所有顶点。
第1步：初始化距离，其实指与D直接连接的点的距离。dis[c]代表D到C点的最短距离，因而初始dis[C]=3，dis[E]=4，dis[D]=0，其余为无穷大。设置集合S用来表示已经找到的最短路径。此时，S={D}。现在得到D到各点距离{D(0)，C(3)，E（4），F（*），G（*），B（*），A(*)}，其中*代表未知数也可以说是无穷大，括号里面的数值代表D点到该点的最短距离。
第2步：不考虑集合S中的值，因为dis[C]=3，是当中距离最短的，所以此时更新S，S={D,C}。接着我们看与C连接的点，分别有B，E，F，已经在集合S中的不看，dis[C-B]=10，因而dis[B]=dis[C]+10=13，dis[F]=dis[C]+dis[C-F]=9，dis[E]=dis[C]+dis[C-E]=3+5=8>4(初始化时的dis[E]=4)不更新。此时{D(0)，C(3)，E（4），F（9），G（*），B（13），A(*)}。
第3步：在第2步中，E点的值4最小，更新S={D，C，E}，此时看与E点直接连接的点，分别有F，G。dis[F]=dis[E]+dis[E-F]=4+2=6（比原来的值小，得到更新），dis[G]=dis[E]+dis[E-G]=4+8=12（更新）。此时{D(0)，C(3)，E（4），F（6），G（12），B（13），A(*)}。
第4步：在第3步中，F点的值6最小，更新S={D，C，E，F}，此时看与F点直接连接的点，分别有B，A，G。dis[B]=dis[F]+dis[F-B]=6+7=13，dis[A]=dis[F]+dis[F-A]=6+16=22，dis[G]=dis[F]+dis[F-G]=6+9=15>12（不更新）。此时{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.
第5步：在第4步中，G点的值12最小，更新S={D，C，E，F，G}，此时看与G点直接连接的点，只有A。dis[A]=dis[G]+dis[G-A]=12+14=26>22(不更新)。{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.
第6步：在第5步中，B点的值13最小，更新S={D，C，E，F，G，B}，此时看与B点直接连接的点，只有A。dis[A]=dis[B]+dis[B-A]=13+12=25>22(不更新)。{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.
第6步：最后只剩下A值，直接进入集合S={D，C，E，F，G，B，A}，此时所有的点都已经遍历结束，得到最终结果{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.
python实现：
将以上的过程使用python来实现。
首先总结一个Dijkstra算法的核心思想，分成两步走：
- 构造一个最短路径数组，每次找到数组中未访问的节点里最小的点
- 以上一步的节点为最新节点，更新起始点到所有点的距离
使用python就是实现这两步即可
MAX= float('inf')
matrix = [
[0,10,MAX,4,MAX,MAX],
[10,0,8,2,6,MAX],
[MAX,8,10,15,1,5],
[4,2,15,0,6,MAX],
[MAX,6,1,6,0,12],
[MAX,MAX,5,MAX,12,0]
]
def dijkstra(matrix, start_node):
#矩阵一维数组的长度，即节点的个数
matrix_length = len(matrix)
#访问过的节点数组
used_node = [False] * matrix_length
#最短路径距离数组
distance = [MAX] * matrix_length
#初始化，将起始节点的最短路径修改成0
distance[start_node] = 0
#将访问节点中未访问的个数作为循环值，其实也可以用个点长度代替。
while used_node.count(False):
min_value = float('inf')
min_value_index = 999
#在最短路径节点中找到最小值，已经访问过的不在参与循环。
#得到最小值下标，每循环一次肯定有一个最小值
for index in range(matrix_length):
if not used_node[index] and distance[index] < min_value:
min_value = distance[index]
min_value_index = index
#将访问节点数组对应的值修改成True，标志其已经访问过了
used_node[min_value_index] = True
#更新distance数组。
#以B点为例：distance[x] 起始点达到B点的距离，
#distance[min_value_index] + matrix[min_value_index][index] 是起始点经过某点达到B点的距离，比较两个值，取较小的那个。
for index in range(matrix_length):
distance[index] = min(distance[index], distance[min_value_index] + matrix[min_value_index][index])
return distance
start_node = int(input('请输入起始节点:'))
result = dijkstra(matrix,start_node)
print('起始节点到其他点距离：%s' % result)