最近一次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越界的运行时错误。