在交通网络中A地和B地之间是否有路相通？在相通的情况下，哪条路最短？现实生活中的交通路线就像一张盘枝错结的网，我们把其抽象成数据结构中的有向图，图中的顶点分别代表着不同的地点，而边上的权值可以代表两个地点之间的距离、交通费用或途中所需要的时间。这样就把现实的问题转化为最短路径的求解问题。求最短路径的算法有很多，本文主要探讨Dijkstra算法。
Dijkstra算法的描述
Dijkstra算法是由荷兰计算机科学家艾兹赫尔·戴克斯特拉发明的。算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说，如果图中的顶点表示城市，而边上的权重表示着城市行经的距离，该算法可以用来找到两个城市之间的最短路径。
算法的思想是通过为每个顶点 v 保留目前为止所找到的从s到v的最短路径来工作的。初始时，原点 s 的路径长度值被赋为 0 （d[s] = 0），同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于 V 中所有顶点 v 除 s 外d[v] = ∞）。当算法结束时，d[v] 中储存的便是从 s 到 v 的最短路径，或者如果路径不存在的话是无穷大。 Dijkstra 算法的基础操作是边的拓展：如果存在一条从 u 到 v 的边，那么从 s 到 v 的最短路径可以通过将边（u, v）添加到尾部来拓展一条从 s 到 u 的路径。这条路径的长度是 d[u] + w(u, v)。如果这个值比目前已知的 d[v] 的值要小，我们可以用新值来替代当前 d[v] 中的值。拓展边的操作一直执行到所有的 d[v] 都代表从 s 到 v 最短路径的花费。这个算法经过组织因而当 d[u] 达到它最终的值的时候每条边（u, v）都只被拓展一次。
算法维护两个顶点集 S 和 Q。集合 S 保留了我们已知的所有 d[v] 的值已经是最短路径的值顶点，而集合 Q 则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 d[u] 值的顶点。当一个顶点 u 从 Q 中转移到了 S 中，算法对每条外接边 (u, v) 进行拓展。
Dijkstra算法的分析
Dijkstra算法要求有向图上的权值是不能为负数的，假设有向图的顶点为N，则该算法的时间复杂度为O（N2）。该算法还能够加以修改以扩充其功能。举例来说，面对一个问题，有时我们可能希望取得数学上的次佳解。为了求得这些次佳解，首先先用原本的该算法求出最佳路径；接下来，我们移除最佳路径中任一段路径，并对剩下来的子集合图再做一次最佳路径计算。对于最佳路径上的每一段路径做一样的操作，我们可以得到许多次佳路径解，将这些路径排序后即为原路径问题的次佳路径解集合。
Dijkstra算法的实现
（一）直接实现
直接实现最简单的实现方法就是，在每次循环中，再用一个循环找距离最短的点，然后用任意的方法更新与其相邻的边，对于空间复杂度，如果只要求出距离，只要n的附加空间保存距离就可以了（距离小于当前距离的是已访问的节点，对于距离相等的情况可以比较编号或是特殊处理一下）。如果要求出路径则需要另外V的空间保存前一个节点，总共需要2n的空间。
（二）二叉堆实现
使用二叉堆(Binary Heap)来保存没有扩展过的点的距离并维护其最小值，并在访问每条边的时候更新，可以把时间复杂度变成O(n+mlogn)。 当边数远小于点数的平方时，这种算法相对来说有很好的效果。但是当m=O(n2)时（有时候表现为不限制边的条数），用二叉堆的优化反倒会更慢。因为此时的复杂度是O(n+n2logn)，大于不用堆的实现的O(n2)的复杂度。 另外此时要用邻接表保存边，使得扩展边的总复杂度为O(m)，否则复杂度不会减小。 空间复杂度：这种算法需要一个二叉堆，及其反向指针，另外还要保存距离，所以所用空间为3n。如果保存路径则为4n。 具体思路：先将所有的点插入堆，并将值赋为极大值(maxint/maxlongint)，将原点赋值为0，通过松弛技术（relax）进行更新以及设定为扩展。
Dijkstra算法的优化
交通系统中地图数据的特点是接点非常多，而边相对较少，每个结点连出去的路段一般最多只有4个，非常符合稀疏图的特征。在这种情况下，利用二叉最小堆来实现优先队列是很有用的。采用堆排序有如下优势：（1）充分利用了现有堆数据，大大降低了数据比较的频繁。堆排序的主要运行时间消耗在建初始堆上，而对于Dijkstra算法来说，整个最短路径的搜索过程中进行的N次堆排序只需要建一个堆，并且在交通系统中，从起始结点直接连接的路段很少，建立堆只需要很少的几条路段，几乎可以在读去所有路段信息时完成，也不需要任何的辅助空间，明显地客服了堆排序的主要缺点，充分地发挥了堆排序的优势。（2）Dijkstra算法中结点最短路径值的修改总是比原来的值小。堆优化Dijkstra算法中采用小根堆即堆顶元素为关键字值最小的元素。堆中某元素的关键字即为结点的最短路径值。修改后，进行堆得重新调整操作时，只需要判断此元素是否需要和父结点进行位置调整。所以Dijkstra算法中堆重新调整的操作要比传统的堆得重新调整过程简单，高效。
【参考文献】
[1] 夏松,韩用顺. GIS中最短路径算法和改进实现[J]. 测绘通报，2004,(9):40-42
[2] 李臣波,刘润涛.一种基于Dijkstra的最短路径算法[J];哈尔滨理工大学学报;2008,03.
[3] 陈靖一.Dijkstra及其改进算法求最短路径的设计与实现[J];舰船电子工程;2010,06.
