Dijkstra算法--单源最短路径问题
Dijkstra以及路径输出
算法原理
Dijkstra算法是利用广度优先搜索思想（BFS）的一种单源最短路径算法，相对于简单粗暴时间复杂度为O(n^3)的Floyed算法，（详情见我另一篇博客 只有五行的Floyed算法及全路径输出），Dijkstra算法的时间复杂度则有好的多，为O(n^2)。
该算法以起点为中心，将相邻边加入到优先队列中，每次取队列中的最短边，利用伸缩操作(relaxation)，更新各点到源点的最近距离(这里用到了贪心算法原理), 存入到一个集合disTo中，该集合中记录每一个点到源点的最近距离，在pathTo集合中，设置此节点的上一节点，如果这点没有被访问过，就加入到优先队列中，就这样重复操作层层向外遍历，最后就可以生成一个最短路径树，对于从该源点到某一点的最短路径问题，只要看该点是否被访问过，被访问过的点说明存在最短路径，回溯pathTo集合，如pathTo(A) = B, B是使A到源点距离最近的相邻点（由贪心算法可知）,pathTo(B) = C , C是使B到源点距离最近的相邻点,反复操作，直到pathTo(X) = 源点。即可得到最短路径
算法的主要函数
节点类
边类：
无向图类：
Dijkstra
实际用例：
结果