Dijkstra算法及优先队列的优化

最短路径问题：针对任意提供的图结构G(V,E)以及指定的起始点S与目标点T，如何确定从S至T之间距离最短的路径。用于解决此类问题的算法包括Dijkstra算法、Bellman-Ford算法、SPFA算法以及Floyd算法。

Dijkstra算法原理解析

该算法主要应用于求解单源最短路径问题，具体而言，给定图G(V,E)以及指定的起始点s，通过特定的计算流程可以确定起点s到图中其余各顶点之间的最短路径长度。

算法执行过程如下：首先建立一个集合S用于存储已访问过的顶点，随后进行n次循环操作（n为图中顶点总数）。

（1）在每次循环中，从未被访问的顶点集合V-S中选取距离起点s最近的顶点u，并将其标记为已访问状态后添加至集合S中。

（2）接着以顶点u作为中间节点，对所有能够从u到达的顶点v进行更新操作，从而优化起点s到这些顶点v之间的最短路径长度。

集合S可通过布尔型数组实现，当vis[i]值为true时表明对应的顶点vi已被访问过。

定义一个int型数组d[]用于存储从起点出发至各个顶点的最短距离。初始状态下，将起点s对应的d[s]设置为0，其余所有位置初始化为一个极大数值。此极大值可采用十六进制表示法0x3fffffff来代替inf，用以表示不可达的状态。

伪代码实现

 Dijkstra(G,d[],s)

    
 {