(二)最短路径算法--Dijkstra
定义：
最短路径问题是指在有权图中的两点之间找到一条权重最小的路径。今天来讲讲比较经典的Dijkstra算法。在开始将算法之前，先对图(网络)做一个基本定义。
图的定义：
对于图中的每个节点，都存在前继节点和后继节点，分别用SUCC(n)和PRED(n)表示，其中n为节点n。如下图：
例如，节点1的后继节点有2和3，节点4的前继节点有2、3和5。箭头旁边的为该条边的权重。
此处所求的最短路径是不包含环的。什么叫做包含环了？举个例子：
比如说这条最短路径，从节点2经过节点3、5，然后又经过节点2，这就是存在环。
算法原理：
我们的目标是求节点到节点的单源最短路径，简单用图1描述一下。我们的目标是要计算从O(O=1)到D(D=4)的最短路径，假设存在这样一条最短路径P(1,4)，那这条最短路径一定是节点4的前继节点(3、2、5)中的一条最短路径加上相应边中最小的一条，即符合：
显然从图1中可以得知是P(1,5)，即从节点5到4是最短的路径。那么P(1,5)要如何求了，同样的道理，那也是从节点5的前继节点中找到一条最短的。
这就类似于动态规划，那么把这个过程正向过来，即我们每次都要找到这样的一个节点，即从起点到该节点的权重之和是所有未访问过的节点中最小的那个，然后从该节点向它的后继节点进行扩展。那么问题是如何找到这个权重之和最小的节点。
这里提供一个解决办法，可以使用斐波那契堆(简称F堆)。它的结构是这样的：
具体实现这里就不做阐述了，这里对后面需要用到的两个方法做一下说明：
FHeap. ExtractMin() 该方法返回堆中最小的元素，并删除该元素
FHeap.Insert(u) 该方法可以向堆中插入一个元素
FHeap.Delete(u) 该方法从堆中删除一个元素
下面是Dijkstra正向扩张的一个步骤图：
实现：
伪代码：
实验：
我们随机从香港路网(1367个节点& 3655条边)中选出100对OD，和没有采用F堆的Dijkstra算法实现进行比较，可以发现，采用F堆可以大大提升算法效率。