Dijkstra算法(加强堆优化)
前言
Dijkstra 算法进行的工作是:在给定图中,以一个给定顶点作为起点,然后找到该顶点到图中所有其它结点的最短路径。该算法解决了图上带权的单源最短路径问题,常见应用场景有路由算法,寻找找到两个目的地之间的最短路径等。
下面来看看它是如何工作的。
流程
以下图为例:
上图中,以 a 点作为起始点。开始流程:
- 以起点 a 为中继点,得到 a->a = 0 ,a->b = 3 ,a->c=1 ,更新表中数据,即上表。
- 中继点 a 到起点 a 的距离已达最小,不会再变动,故将其锁住。从表中未锁节点中找到值最小的,即 c 点,以其作为中继点。发现a->c->b = 2 < 3 ,a->c->d = 3 < ∞,a->c->f = 51 < ∞,更新表中数据,即上表。
- 中继点 c 到起点 a 的距离已达最小,不会再变动,锁住。从表中未锁节点中找到值最小的,即 b 点,以其作为中继点。发现 a->c->b->d = 12 ,比 a->c->d 大,因此不更新。
- 同样,b 锁住,从表中未锁节点中找到值最小的,即 d 点,以其作为中继点。发现 a->c->d->e = 4 < ∞,更新表。
- 同样,d 锁住,从表中未锁节点中找到值最小的,即 e 点,以其作为中继点。得到 a->c->d->e->f = 7 < 51,a->c->d->e->g = 13 < ∞,更新表。
- 同样,e 锁住,从表中未锁节点中找到值最小的,即 f 点,以其作为中继点。得到 a->c->d->e->f->g = 13 ,与之前相同,不必更新。
- 同样,f 锁住,从表中未锁节点中找到值最小的,即 g 点,以其作为中继点。没有更短的路径,结束。
所以最后的距离表如下:
该表即为图中各点到 a 点的最短距离。
不难发现上面的流程是以中继点为跳板去发现其他可能的最短路径。且算法的核心思想在于:两点之间的最短路径也包含了路径上其他顶点间的最短路径!
算法实现
在上面的流程中,不断有一个动作:“从表中未锁节点中找到值最小的”,即每一次循环我们都必须弹出值最小的未锁节点,这似乎可以用小根堆来完成。实际上,单纯的小根堆无法完成上述工作,这是因为表是时刻在更新的,普通的堆无法完成这个动态更新的过程(因为如果你直接修改普通堆中的数据,而不及时地调整堆结构,整个堆就会报废)。而加强堆就能够动态调整堆中被修改的数据。
#include<unordered_map>
#include<vector>
#include"../header/heapEnhanced.h"
#include"../header/graph.h"
struct wrap
{
graphNode* node;
int dis;
wrap(graphNode* _node, int _dis):node(_node), dis(_dis){}
};
struct cmptor
{
bool operator()(const wrap* a, const wrap* b) {
return a->dis > b->dis;//小顶堆
}
};
void addOrUpdateOrIgnore(heapGreater<wrap*, cmptor> &heap, unordered_map<graphNode*, wrap*> &help, graphNode* node, int dis)
{
if(help.find(node) == help.end())//如果node之前没有入过堆,表示距离起点无穷远,直接添加新纪录
{
wrap* wp = new wrap(node, dis);
heap.push(wp);
help.emplace(node, wp);//标记已入堆
}
else //如果已经入过堆,则比较新距离dis和旧距离wp->dis,前者小则更新;否则忽略
{
wrap* wp = help.find(node)->second;
if(wp->dis > dis)
{
wp->dis = dis;
heap.modify(wp, wp);//更新堆中数据,自动调整堆结构
}
}
}
unordered_map<graphNode*, int> disMap(graphNode* node)
{
unordered_map<graphNode*, int> retMap;//返回值
unordered_map<graphNode*, wrap*> help;//用来判断哪些节点已经入过堆,没有入过堆的表示距离∞
heapGreater<wrap*, cmptor> heap;//加强堆,存放未锁节点
wrap* nd = new wrap(node, 0);//起点到起点的距离为0
heap.push(nd);//初始时刻,起点入堆
help.emplace(node, nd);//标记已经入过堆
while(!heap.empty())
{
nd = heap.pop();//弹出未锁节点中距离最小的节点,作为中继点;弹出后该点即被锁住
retMap.emplace(nd->node, nd->dis);//中继点本身到起点距离已最短,直接加入结果
for(auto edge : nd->node->edges)
{//以中继点为跳板,试探相邻边是否构成到对应节点的最短路径
addOrUpdateOrIgnore(heap, help, edge->to, nd->dis + edge->weight);
}
}
for(auto n : help)
delete n.second;
return retMap;
}
-
由于需要记录节点到起点的距离,所以需要将
graphNode
包装成wrap
结构体。 -
我们的加强堆默认是大根堆,所以这里需要传入比较器
cmptor
将加强堆初始化为小根堆。不了解比较器的朋友请参见比较器与仿函数
-
disMap
是主逻辑函数,addOrUpdateOrIgnore
是关键的辅助函数,工作流见注释。
int main()
{ //这里是无向图,有向图也可。
vector<vector<int>> vec = {
{3, 'a', 'b'},
{3, 'b', 'a'},
{1, 'a', 'c'},
{1, 'c', 'a'},
{1, 'b', 'c'},
{1, 'c', 'b'},
{10, 'b', 'e'},
{10, 'e', 'b'},
{2, 'c', 'e'},
{2, 'e', 'c'},
{50, 'c', 'f'},
{50, 'f', 'c'},
{1, 'e', 'g'},
{1, 'g', 'e'},
{6, 'f', 'h'},
{6, 'h', 'f'},
{3, 'f', 'g'},
{3, 'g', 'f'},
{9, 'g', 'h'},
{9, 'h', 'g'}
};
graph gra = graphAdaptor(vec);
auto startNode =gra.nodes['a'];
auto map = disMap(startNode);
char ch;
for(auto n : map)
{
ch = n.first->value;
std::cout << "node: " << ch << " distance: " << n.second << std::endl;
}
}
输出:
node: g distance: 4
node: h distance: 13
node: b distance: 2
node: f distance: 7
node: e distance: 3
node: c distance: 1
node: a distance: 0
本文链接:
/archives/Dijkstra
版权声明:
本站所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自
后端技术分享!
喜欢就支持一下吧