一次令人自闭的算法作业

最近一次Data Structure & Algorithm课程的作业是要求实现Dijkstra算法，并且其中的排序部分要使用最小堆来实现。

Dijkstra的基本思路如下

1. 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为”起点s到该顶点的距离”[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。

2.从U中选出”距离最短的顶点k”，并将顶点k加入到S中；同时，从U中移除顶点。

3.更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。

4.重复步骤(2)和(3)，直到遍历完所有顶点。

我们的作业要求是在步骤2中的“选出距离最短的顶点”要用堆来实现。也就是说，我们需要维护一个最小堆，里面包含有起点到各个尚未访问到的顶点的（目前为止的）最短距离。每一次更新各个顶点到起点的距离时，都要更新堆中所有顶点的值。这样，每次寻找距离最短的顶点时，直接取出堆的根即可，省去了每次都要遍历一遍来寻找最小值。

我们要求的实现逻辑是这样的：维护一个如下的routing table，其中存储了每个节点的id，是否已经访问过，到出发点的最短距离，和该节点在堆中对应的位置。每次访问图中的一个节点时，都要在routing table中更新该节点及其所有后继节点的距离和其他信息。

node	0	1	2
is_visited	true	true	false
cost	0	1	3
heap_position	0	1	2

我写完提交之后，被告知我的solution在小用例上部分正确，大用例上报vector越界的运行时错误。

那就开工吧！

我首先尝试了几个相对小的用例，但是无法复现问题。于是我用生成器生成了一个有100条边的图，果然vector越界的问题出现了。经过单步调试之后发现在图没有走完的时候，堆中的元素已经被取干净了。

又经过了长达数十分钟的单步调试，我终于发现问题在于生成的测试样例——其中一些节点只有出度而没有入度，也就是说，有些点是永远无法到达的，而我的逻辑是将所有点走完之后才能结束循环，因此堆中的元素会在循环跳出之前就消耗掉，导致vector越界。

我的解决方法十分粗暴——当堆中元素为空时即跳出循环，这样就不会有越界问题了。

然而事情并没有结束。

修改之后，我发现在小的用例上能够得出正确结果，而在稍大一些的用例上虽然不会有运行时错误，但是答案却是错的。最麻烦的事情是——由于用例过大不可能单步去调，所以完全没法定位问题出在哪。我绞尽脑汁想了一些奇奇怪怪的小型用例，但是还是无法复现问题。

于是我只能把程序拆解成若干部分，依次排查问题。

我仿照单元测试的方法，单独写了一个函数去调用堆的插入，删除，和修改这三个方法，并且通过随机生成巨大的测试样例来验证堆是否合法。经过一通测试还真的发现了问题，我发现从堆中移除和修改元素的方法都存在缺陷，有时会导致堆不合法。经过修改之后，和堆相关的所有方法终于可以确定可用了。

然而事情还是没有结束。当我满心欢喜地再次测试整个程序时，我发现虽然已经修正了一些错误，但是输出的答案依然没变。于是现在又进入到了死胡同。

由于和堆相关的算法都已经确认正确，根据福尔摩斯推理法，问题只能出在Dijkstra算法本身的实现上——即使看起来这里不应该出现问题。然而我把我实现的算法和课上的笔记和网上的资料仔细对比，发现算法实现并没有问题。

到目前为止，我所推测的所有可能性都已经被推翻，所以也只能单步调试了。我选了几个可能出现问题节点打了断点，然而还是没有发现问题。直到无意间，我发现在循环结束时，routing table中的一部分节点还没有被访问到。

经过一番检查发现，由于每次更新堆中节点的值的时候，堆中节点的位置会改变，然而routing table中记录的该节点在堆中的位置却没有改变。导致堆中一些节点的值被错误地更新而被提前取出。解决方法很简单，只要每次查找堆中元素时使用值查找而不是使用索引查找即可。只不过这个做法有些tricky，并且会降低一些性能，不过确实能够解决问题。