最短路径之Dijkstra算法

Dijkstra算法是一个单源最短路径算法，也就是一次只能求从一个顶点到其余各顶点的最短路径，不支持存在负权的图，使用数组实现的时间复杂度是O(V²)，使用优先队列实现的时间复杂度是O((V+E)LogV)，V是顶点的数量，E是边的数量。

主要思路是从起点开始，采用贪心算法的策略，每次选取距离起始点最近且未访问过的顶点v，然后比较其它顶点原来与起点的距离，和以顶点v作为中转点的之后该点与起点的距离，如果比原来的距离短，则更新。

首先定义一个数组distance，数组中第i个元素代表起始点到第i个顶点当前的最短距离，我们通过不断的寻找最短的中转点来更新这个数组，如下所示

上面的示例，使用Dijkstra算法求最短路径的两种代码实现