前言

Dijkstra 算法进行的工作是：在给定图中，以一个给定顶点作为起点，然后找到该顶点到图中所有其它结点的最短路径。该算法解决了图上带权的单源最短路径问题，常见应用场景有路由算法，寻找找到两个目的地之间的最短路径等。

下面来看看它是如何工作的。

流程

以下图为例：

上图中，以 a 点作为起始点。开始流程：

1. 以起点 a 为中继点，得到 a->a = 0 ，a->b = 3 ，a->c=1 ，更新表中数据，即上表。

2. 中继点 a 到起点 a 的距离已达最小，不会再变动，故将其锁住。从表中未锁节点中找到值最小的，即 c 点，以其作为中继点。发现a->c->b = 2 < 3 ，a->c->d = 3 < ∞，a->c->f = 51 < ∞，更新表中数据，即上表。

3. 中继点 c 到起点 a 的距离已达最小，不会再变动，锁住。从表中未锁节点中找到值最小的，即 b 点，以其作为中继点。发现 a->c->b->d = 12 ，比 a->c->d 大，因此不更新。

4. 同样，b 锁住，从表中未锁节点中找到值最小的，即 d 点，以其作为中继点。发现 a->c->d->e = 4 < ∞，更新表。

5. 同样，d 锁住，从表中未锁节点中找到值最小的，即 e 点，以其作为中继点。得到 a->c->d->e->f = 7 < 51，a->c->d->e->g = 13 < ∞，更新表。

6. 同样，e 锁住，从表中未锁节点中找到值最小的，即 f 点，以其作为中继点。得到 a->c->d->e->f->g = 13 ，与之前相同，不必更新。

7. 同样，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