【数据结构与算法】图的最短路径算法实现：Dijkstra && Bellman

前言

​ 最短路径问题：从在带权有向图 G 中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。

Ⅰ. 单源最短路径 – Dijkstra 迪杰克斯拉算法

​ 单源最短路径问题：给定一个图 G=(V，E)，求源结点 s∈V 到图中每个结点 v∈V 的最短路径。Dijkstra 算法就适用于解决带权重的有向图上的单源最短路径问题，同时算法要求图中所有边的权重非负。一般在求解最短路径的时候都是已知一个起点和一个终点，所以使用 Dijkstra 算法求解过后也就得到了所需起点到终点的最短路径。

算法简介

​ Dijkstra 算法是用来解决 单源最短路径的算法，即在一个图中找出一个点 N，找出以该点为起点到其他所有点的最短路径。但是如果想找到两个顶点 A 和 C 之间的最短路径时，Dijkstra 算法可能同时找到到达其它顶点（例如顶点B）的最短路径，这一点将在算法演示的时候详细解释。同时 Dijkstra 算法 无法适用于含有负权重的图。

​ 时间复杂度：O(V^2)

算法步骤

1. 维护一个数组 dist 来储存起点到各个顶点的最短距离，一个数组 pPath 来存储每个节点在最短路径中的上一个节点的下标（方便后面的打印），一个数组 S 来用 bool 值来表示每个节点是否已经被确定。
2. 初始化上面的数组，dist 中起点默认为 0，其他点默认为无穷大；pPath 中起点默认为 0，其他点默认为 -1；S 中默认所有点为 false，表示还没被确定。
3. 利用循环遍历 _vertexs.size() 次，每次选择未确定顶点中距离最近的，将该点在 S 数组中设为 true，表示确认了。
4. 接着进行松弛调整，也就是找到与当前选择的顶点 u 邻接的点 k ，计算数组 dist 中存储的到达 k 点的距离是否小于起点经过 u 到达 k 点的距离，即判断 dist[u] + _matrix[u][k] <= dist[k]，是的话则更新邻接点 k 在 dist 中的值为 dist[u] + _matrix[u][k]，并调整 pPath 中 k 点的父亲节点下标，否则继续寻找下一个与 u 相邻的点，重复该步骤直到遍历完 u 的所有邻接点。
5. 重复步骤 3、4 直至遍历所有节点都访问过。

注意事项：

1. Dijkstra 算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路径的最短路径
2. 为什么不采用优先级队列来找每次最短路径中的最小顶点呢❓❓❓ 因为我们在找到这个顶点后会做松弛算法，那么可能会调整到其他顶点的一个权值，所以这个时候我们也得更新优先级队列中的顶点权值，那也是比较麻烦的，所以这里采用简便一点的实现，直接使用循环，当然这样子时间复杂度会相对高一点！

代码实现

代码语言：javascript代码运行次数：0运行复制

// Dijkstra算法
// 其中src代表单源节点
// dist数组是存放src到每个节点的最短路径距离
// pPath数组是存放每个节点的最短路径中的上一个节点下标
void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
{
    // 一些初始化工作
    size_t srci = GetVertexIndex(src);
    size_t n = _vertexs.size();
    dist.resize(n, MAX_W);
    dist[srci] = W(); // 将单源节点先设为默认值
    pPath.resize(n, -1);
    pPath[srci] = W();

    // S中true表示该点已经确定
    vector<bool> S(n, false);

    // 这里采用直接遍历所有点，再在循环体中再来寻找最小值的方式
    // 因为如果是用优先级队列的话，不好调整
    for (size_t i = 0; i < n; ++i)
    {
        // 贪心算法：srci到不在S中路径最短的那个顶点u
        size_t u = srci;
        W min = MAX_W;
        for (size_t j = 0; j < n; ++j)
        {
            if (S[j] == false && dist[j] < min)
            {
                u = j;
                min = dist[j];
            }
        }
        S[u] = true; // 将当前得到的节点设置为已确定

        // 现在有了那个当前最短边的顶点的下标
        // 所以我们直接遍历这个点的邻接点
        // 并对这些邻接点进行松弛调整
        for (size_t k = 0; k < n; ++k)
        {
            // 1、若邻接点为确定的节点了，那么不需要调整
            // 2、若不相通也不需要调整
            // 3、若当前权值加上与邻接点的边的权值大于了原来邻接点的权值，那么也不需要调整
            if (S[k] == false
                && _matrix[u][k] != MAX_W
                && dist[u] + _matrix[u][k] < dist[k])
            {
                dist[k] = dist[u] + _matrix[u][k];
                pPath[k] = u; // 注意别忘了更新路径
            }
        }
    }
}

void PrintShortPath(const V& src, const vector<W>& dist, const vector<W>& pPath)
{
    size_t srci = GetVertexIndex(src);
    size_t n = _vertexs.size();

    for (size_t i = 0; i < n; ++i)
    {
        if (srci != i)
        {
            vector<size_t> path;
            size_t parenti = i;
            while (parenti != srci)
            {
                path.push_back(parenti);
                parenti = pPath[parenti];
            }
            path.push_back(srci);

            // 先逆置一下，因为当前的访问顺序是从后到前的
            reverse(path.begin(), path.end());
            for (auto e : path)
            {
                cout << _vertexs[e] << "->";
            }
            cout << dist[i] << endl;
        }
    }
}

void TestGraphDijkstra()
{
    const char* str = "syztx";
    Graph<char, int, INT_MAX, true> g(str, strlen(str));
    g.AddEdge('s', 't', 10);
    g.AddEdge('s', 'y', 5);
    g.AddEdge('y', 't', 3);
    g.AddEdge('y', 'x', 9);
    g.AddEdge('y', 'z', 2);
    g.AddEdge('z', 's', 7);
    g.AddEdge('z', 'x', 6);
    g.AddEdge('t', 'y', 2);
    g.AddEdge('t', 'x', 1);
    g.AddEdge('x', 'z', 4);
    vector<int> dist;
    vector<int> parentPath;
    g.Dijkstra('s', dist, parentPath);
    g.PrintShortPath('s', dist, parentPath);

    // 图中带有负权路径时，贪心策略则失效了。
    // 测试结果可以看到s->t->y之间的最短路径没更新出来
    /*const char* str = "sytx";
		 Graph<char, int, INT_MAX, true> g(str, strlen(str));
		 g.AddEdge('s', 't', 10);
		 g.AddEdge('s', 'y', 5);
		 g.AddEdge('t', 'y', -7);
		 g.AddEdge('y', 'x', 3);
		 vector<int> dist;
		 vector<int> parentPath;
		 g.Dijkstra('s', dist, parentPath);
		 g.PrinrtShotPath('s', dist, parentPath);
	*/
}

// 运行结果：
s->y->5
s->y->z->7
s->y->t->8
s->y->t->x->9

Ⅱ. 单源最短路径 – Bellman-Ford 贝尔曼-福特算法

​ Dijkstra 算法只能用来解决正权图的单源最短路径问题，但有些题目会出现负权图。这时这个算法就不能帮助我们解决问题了，而 bellman—ford 算法 可以解决负权图的单源最短路径问题。它的优点是可以解决有负权边的单源最短路径问题，而且 可以用来判断是否有负权回路。它也有明显的缺点，它的 时间复杂度 O(N*E) (N是点数，E是边数) 普遍是要高于 Dijkstra 算法的。

​ 像这里如果我们使用邻接矩阵实现，那么遍历所有边的数量的 时间复杂度就是 O(N^3)，这里也可以看出来 Bellman-Ford 就是一种暴力求解更新。

​ 但 Bellman—Ford 算法可以进行若干种优化，提高效率，有兴趣的话可以了解一下（后边我们会加入第一种优化）：

1. 循环的提前跳出
   • 在实际操作中，贝尔曼-福特算法经常会在未达到 V-1 次前就出解，V-1 其实是最大值。于是可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环，进行负权环判定。
2. 队列优化（SPFA算法）
   • 主条目：最短路径快速算法
   • 西南交通大学的段凡丁于 1994 年提出了用队列来优化的算法。松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上，用一个队列记录松弛过的节点，可以避免了冗余计算。原文中提出该算法的复杂度为 O(k*E)，k 是个比较小的系数，但该结论未得到广泛认可。

基本原理

​ 逐遍的对图中每一条边去迭代计算起始点到其余各点的最短路径，执行 N-1 遍，最终得到起始点到其余各点的最短路径，有点类似于冒泡排序的思想。（N为连通图结点数）

与迪杰斯特拉算法的区别

• 迪杰斯特拉算法是借助 贪心思想，每次选取一个未处理的最近的结点，去对与他相连接的边进行松弛操作；贝尔曼福特算法是直接对所有边进行 N-1 遍松弛操作，也就是 暴力破解。
• 迪杰斯特拉算法要求边的权值 不能是负数；贝尔曼福特算法边的权值 可以为负数，并 可检测负权回路。

名词解释

• 松弛操作：不断更新最短路径和前驱结点的操作。
• 负权回路：绕一圈绕回来发现到自己的距离从 0 变成了负数，到各结点的距离无限制的降低，停不下来。