源代码地址: https://github.com/YdreamW/20ss/tree/master/ads/project1_Fibheap%26ShortestPath
题目要求
Shortest path problems are ones of the most fundamental combinatorial optimization problems with many applications, both direct and as subroutines in other combinatorial optimization algorithms. Algorithms for these problems have been studied since 1950’s and still remain an active area of research.
In this project you are supposed to compute the shortest paths using Dijkstra’s algorithm. The implementation shall be based on a min-priority queue, such as a Fibonacci heap. The goal of the project is to find the best data structure for the Dijkstra’s algorithm.
Your tasks are:
- (1) Implement the algorithm with at least two different heap structures, while Fibonacci heap must be one of them.
- (2) Use the USA road networks for evaluation. The data sets can be downloaded from http://www.dis.uniroma1.it/challenge9/download.shtml which provides the benchmarks for the 9th DIMACS Implementation Challenge. (Note: you must only list the download links of these test data sets instead of uploading them with your reports.)
- (3) At least 1000 pairs of query are required in evaluating the run times of the algorithm with various of implementations.
###Grading Policy:
Programming: Implement Dijkstra’s algorithm with Fibonacci heap and other heaps (6 pts.). Write a test of performance program (3 pts.). All the codes must be sufficiently commented.
Testing: Provide the necessary inputs for testing and give the run time table (2 pts.). Plot the run times vs. input sizes for illustration (2 pts.). Write analysis and comments (3 pts.).
Documentation: Chapter 1 (1 pt.), Chapter 2 (2 pts.), and finally a complete report (1 point for overall style of documentation).
斐波那契堆: (参考:斐波那契堆)
斐波那契堆(Fibonacci heap)是堆中一种,它和二项堆一样,也是一种可合并堆;可用于实现合并优先队列。斐波那契堆比二项堆具有更好的平摊分析性能,它的合并操作的时间复杂度是O(1)。
与二项堆一样,它也是由一组堆最小有序树组成,并且是一种可合并堆。
与二项堆不同的是,斐波那契堆中的树不一定是二项树;而且二项堆中的树是有序排列的,但是斐波那契堆中的树都是有根而无序的。

- 基本定义
FibNode是斐波那契堆的节点类,它包含的信息较多。key是用于比较节点大小的,degree是记录节点的度,left和right分别是指向节点的左右兄弟,child是节点的第一个孩子,parent是节点的父节点,marked是记录该节点是否被删除第1个孩子(marked在删除节点时有用)。
FibHeap是斐波那契堆对应的类。min是保存当前堆的最小节点,keyNum用于记录堆中节点的总数,maxDegree用于记录堆中最大度,而cons在删除节点时来暂时保存堆数据的临时空间。
下面看看斐波那契堆的内存结构图。

从图中可以看出,斐波那契堆是由一组最小堆组成,这些最小堆的根节点组成了双向链表(后文称为”根链表”);斐波那契堆中的最小节点就是”根链表中的最小节点”!
- 插入操作
插入操作非常简单:插入一个节点到堆中,直接将该节点插入到”根链表的min节点”之前即可;若被插入节点比”min节点”小,则更新”min节点”为被插入节点。

上面是插入操作的示意图。
斐波那契堆的根链表是”双向链表”,这里将min节点看作双向联表的表头(后文也是如此)。在插入节点时,每次都是”将节点插入到min节点之前(即插入到双链表末尾)”。此外,对于根链表中最小堆都只有一个节点的情况,插入操作就很演化成双向链表的插入操作。
- 合并操作
合并操作和插入操作的原理非常类似:将一个堆的根链表插入到另一个堆的根链表上即可。简单来说,就是将两个双链表拼接成一个双向链表。

- 取出最小节点
抽取最小结点的操作是斐波那契堆中较复杂的操作。
(1)将要抽取最小结点的子树都直接串联在根表中;
(2)合并所有degree相等的树,直到没有相等的degree的树。

上面是取出最小节点的示意图。图中应该写的非常明白了,若有疑问,看代码。
- 减小节点值
减少斐波那契堆中的节点的键值,这个操作的难点是:如果减少节点后破坏了”最小堆”性质,如何去维护呢?下面对一般性情况进行分析。
(1) 首先,将”被减小节点”从”它所在的最小堆”剥离出来;然后将”该节点”关联到”根链表”中。 倘若被减小的节点不是单独一个节点,而是包含子树的树根。则是将以”被减小节点”为根的子树从”最小堆”中剥离出来,然后将该树关联到根链表中。
(2) 接着,对”被减少节点”的原父节点进行”级联剪切”。所谓”级联剪切”,就是在被减小节点破坏了最小堆性质,并被切下来之后;再从”它的父节点”进行递归级联剪切操作。
而级联操作的具体动作则是:若父节点(被减小节点的父节点)的marked标记为false,则将其设为true,然后退出。
否则,将父节点从最小堆中切下来(方式和”切被减小节点的方式”一样);然后递归对祖父节点进行”级联剪切”。
marked标记的作用就是用来标记”该节点的子节点是否有被删除过”,它的作用是来实现级联剪切。而级联剪切的真正目的是为了防止”最小堆”由二叉树演化成链表。
(3) 最后,别忘了对根链表的最小节点进行更新。

- 增加节点值
增加节点值和减少节点值类似,这个操作的难点也是如何维护”最小堆”性质。思路如下:
(1) 将”被增加节点”的”左孩子和左孩子的所有兄弟”都链接到根链表中。
(2) 接下来,把”被增加节点”添加到根链表;但是别忘了对其进行级联剪切。

- 删除节点
删除节点,本文采用了操作是:”取出最小节点”和”减小节点值”的组合。
(1) 先将被删除节点的键值减少。减少后的值要比”原最小节点的值”即可。
(2) 接着,取出最小节点即可。