转-Dijkstra/Johnson’s algorithm and Fibonacci heap(fib heap)

April 27, 2007 10:54 · Filed under 技术杂谈

Dijkstra’s algorithm use Fibonacci heap to implement
董明峰 2005/10/25
讨论内容：
(1)Dijkstra’s algorithm是解决single source shortest path问题的一种算法。single source shortest path是探讨从一个起始点s到其它每个端点v的最短路径。假设p[v]是用来存放从s到每个点v的最短距离，例如p[s]=0，代表从s到s的最短距离 是0；假设总共有n个点，m个边(点到点的距离)所以必须要跑 n次，才可以算完每个点；而每次的计算包含两部分，一部分是求目前距离s最近的点(该点的p[v]值还不是最短距离的值)，另一部分是修改p[v]的值； 举个例子：假设n = 4，求v1到其它每个点的最短距离，一开始初始化p[v1]=0，p[v2]=2，p[v3]=4，p[v4]=∞(如果一开始v1无法直接到达该点，必 须透过其它点才可到达，p[v]值就给∞)；接着开始去跑n次循环，每次循环包含两部分：

1.求目前距离v1最近的点(该点的p[v]值还不是最短距离的值)，也就是p[v2]=2，这部分也必须要跑n次，去求p[v]目前最小的值。
2.求得p[v2]之后，也就确定v1v2的最短距离，接着必须更新其它还未确定的p[v]值；假设v2有直接的路径可以到v3，所要花的距离是1，所 以从v1 v2 v3的总距离是3，比v1 v3的距离4还要近，所以修改p[v3]=3。这部分虽然也是要跑n次，但从实际上来看，他会跑每个边(点到点的距离)，所以时间复杂度是O(m)

重复执行该循环，直到每个点的最短距离都求得。而Dijkstra’s algoritm一般是用相邻矩阵去implement，所需花的时间复杂度是m + n2 ，所以是O(n2)。

(2)改用Fibonacci heap(简称F-heap)来implement Dijkstra’s algorithm。 F-heap跟一般heap不太一样，他有特殊的数据结构来表示每个node，使得执行效能比一般heap快了许多，原本heap在 insert，delete min，decrease key，所需花费的时间复杂度都是O(log n)。 F-heap的特殊数据结构，除了在delete min or delete上面，依旧需要O(log n)，其余的所需花的时间都是O(1)。若用F-heap来implement Dijkstra’s algorithm，一开始要对n个nodes初始化，要做n次的insert；接下来进到n次循环，有两部分动作要执行，第一部分在求目前距离s最近的 点这部分，也就是做delete min，花费的时间是O(n log n)；另一部分是修改node的key值，也就是做decrease key，花费的时间是O(m)；所以总共所需的时间复杂度是O(m + n log n)。

心得感想：
目前应该还有许多的算法可能是用矩阵或者是heap来implement的，也许可能是其它的数据储存型态；然而F-heap的应用上似乎还不是很高，可 能是因为他还需要比较复杂的数据结构，所以不知对于其它的应用上是否有实际的帮助；或者是否能简化他的数据结构，而依旧能保持相同的效率？

Johnson’s algorithm
* Johnson’s 演算法利用reweighing来除去负边，使得该图可以套用Dijkstra演算法，来达到较高的效能。
* Reweighing是将每个点v设定一个高度h(v)，并且调整边的weight function w(u,v)成为w’(u,v)=w(u,v)+h(u)-h(v)。
* 令δ‘(u,v)如此调整之后的最短距离，则原先的最短距离δ(u,v)=δ‘(u,v)-h(u)+h(v)。

复杂度分析
* 执行一次Bellman-Ford。O(|V||E|)。
* 执行|V|次Dijkstra。
o 使用Fibonacci heap，总计O(|V|2log|V|+|V||E|) 。
o 使用Binary heap，总计O(|V||E|log|V|)。
* 当|E|足够小，比Warshall-Floyd快。