最短路径dijkstra算法及其优先队列的优化

最短路径问题：对任意给出的图G(V,E)和起点S，终点T，如何求从S到T的最短路径。解决最短路径问题的算法有Dijkstra算法，Bellman-Ford算法，SPFA算法和Floyd算法。

主要用于解决单源最短路径问题，即给定图G(V,E)和起点s，通过算法得到S到达其他每个顶点的最短距离。

算法步骤：设置集合S存放已被访问的顶点，然后执行n次下面的每个步骤(n为顶点个数)

（1）每次从集合V-S（未被访问的顶点）中选择与起点S的最短距离最小的一个顶点记为u，访问并加入集合s

（2）之后，令顶点u为中介点，优化起点S与所有从u可以到达的顶点v之间的最短距离。

集合S可以用一个布尔型数组来实现，当vis[i]==true时表示顶点vi已被访问。

令int型数组d[]表示从起点到任意顶点的最短距离，初始时给起点s的d[s]赋值为0，其余为很大的值，可以用二进制编码的十六进制0x3fffffff来表示inf，即不可到达。