Dijkstra算法
算法思路：
- Dijkstra算法采用的是一种贪心的策略,声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T,初始时,原点 s 的路径权重被赋为 0 （dis[s] = 0）.若对于顶点 s 存在能直接到达的边（s,m）,则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大.初始时,集合T只有顶点s.
- 然后,从dis数组选择最小值dis[i]（vi ∈V-S ）,则该值就是源点s到该值对应的顶点的最短路径,并且把该点加入到T中,OK,此时完成一个顶点.
- 然后,我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短,如果是,那么就替换这些顶点在dis中的值.
- 然后,又从dis中找出最小值dis[i]（vi ∈V-S ）,重复上述动作,直到T中包含了图的所有顶点.
个人理解原理：
直接连接的权值最小值一定比多结点连接小（权值均为正）,多结点连接的权值最小值一定比更多结点连接小,这样便可确定两点路径的最小值
例如：
首先第一步,我们先声明一个dis数组,该数组初始化的值为：
我们的顶点集T的初始化为：T={v1},选取dis数组中的最小值,将结点加入T,则V1到V3的最短距离即为10.因为是dis数组当前的最小值,对于比大的边来说,之后不可能让V1通过他们获得比值更小的路径,因为权值均为正.特别的,对于值为无穷大的路径,之后其路径值必大于当前的最小路径,因为这些结点间即使存在路径,也是通过当前存在路径的结点沟通起来的,其路径值必然大于当前的最小路径值.多结点连接同理.
为什么Dijkstra算法中不能有负权值？
因为如果允许有负权值,可能出现当与S内某点（记作a）以负边相连的点（记作b）确定最短路径时,它的最短路径长度加上这条负边的权值结果小于a原先确定的最短路径长度.而此时a无法更新.因为新的vi 必须从顶点集合V-S中选出,因此a的dist不可能被刷新.
部分内容转自：最短路径问题—Dijkstra算法详解 侵删
本人水平有限,有错误的地方请指正,谢谢！