最短路径

​ 在图中，不可避免要解决的一个问题就是计算两点之间的最短路径，对于图结构来说，两个点之间不一定只有一条路径，那么如何才能找出最短的那一条就是图中最短路径问题。最短路径问题在实际生活中应用十分广泛。接下来主要介绍两种较为常用的最短路径算法—$Dijkstra$算法和$Floyd$算法。

文章目录

• 最短路径
• • 迪杰斯特拉$Dijkstra$算法
  • $Floyd$算法
  • 最小生成树与最短路径的区别

​ 首先需要对最短路径问题进行一些说明，图的类型既可以是有向图也可以是无向图，为了统一，之后统一使用有向图来进行解释。接下来也对于该问题中的一些定义进行区分：

1. 路径长度：一条路径上所经过的边的数目
2. 带权路径长度：路径上所经过边的权值之和
3. 最短路径：带权路径长度值最小的那条路径

迪杰斯特拉$Dijkstra$算法

​ $Dijkstra$算法是一种较为经典的最短路径求解算法，它的整体思路和前面的$Prim$算法非常相似，但是又有一些不同之处。接下来首先对$Dijkstra$算法的整体流程进行一个大致的了解：

1. 设置两点顶点的集合$U$和$T$，集合$U$中存放已找到最短路径的顶点，集合$T$中存放当前还未找到的最短路径的顶点。
2. 初始状态时，集合$U$中只包含源点，设为$v_0$。
3. 然后从集合$T$中选择到源点$v_0$路径长度最短的顶点$u$加入到集合$U$中。
4. 集合$U$中每加入一个新的顶点$u$都要修改源点$v_0$带集合$T$中剩余顶点的当前最短路径值，集合$T$中各顶点的新的当前最短路径长度值，为原来的当前最短路径长度值与从源点过顶点$u$到达该顶点的带权路径长度中的较小者。
5. 回到3，此过程不断重复，直到集合$T$中的顶点全部加入到集合$U$中为止。

从上述算法流程中可以看出，$Dijkstra$算法和$Prim$算法的相似之处在于在寻找路径时，都是逐点添加，添加之后也需要重新更新路径。

​ 该算法在计算的时候将所有的点分为两个集合，一个是目标点集$U$，初始时只有起点，$Dijkstra$算法的功能是，给定一个起点，计算其到其他所有点的最短路径，也就是$1ton$的问题。之后在集合$T$中找到起点$v_0$能够达到的，且距离最短的点，将其加入到$U$中，之后根据新加入的点，重新计算一次$v_0$到$T$中剩余点的当前最短距离即可。

​ 接下来通过一个例子来对该算法进行更进一步的理解。

​ 上述例子中，有图中圆圈中的字母代表节点的信息，圆圈上面的内容代表源点到其最短距离以及前驱节点，前驱节点用于后续重现最短路径。这里主要是使用到了一个简单的定理，**如果起点$v_0$到目标点$u$之间的某一条路径是最短路径，那么在该路径上面，任何一个点$u^{\prime }$到$v_0$的路径都是$u^{\prime }$到$v_0$的最短路径。**这个证明十分简单，使用反证法即可。那么这里在记录最短路径的信息时，如果需要重现路径中的顶点，那么只需要对于每一个结点设置一个前驱结点即可。

​ 接下来继续查看一个例子，这里使用表格的形式来对整个算法流程进行分析。

​ 在对该算法有了一定的理解之后，接下来就是考虑如何使用代码来实现它。由于该算法和$Prim$算法十分相近，所以在实现部分和$Prim$算法的实现部分基本一致，除了多了一个前驱数组，在初始化时，依旧是根据起点和邻接矩阵来对所有的距离进行初始化。对于源点到$T$中点的最短距离，也是借助一个访问数组$visit$和距离数组$dis$来进行保存，$visit[i]=false$代表第$i$个点在集合$T$中。之后在每次循环中，找出距离最短的，然后将其加入到集合$U$中。最后就是最关键的一步，也就是根据新加入的点来更新到$T$中剩余点的最短距离，这一步和$Prim$算法中的判断条件不同，需要注意。

​ 在具体实现路径重现的时候，主要是借助前驱数组和栈来进行实现，具体代码如下所示。

// Dijkstra算法
    void Dijkstra(int begin)
    {
        int minpath = INF;
        int path[MAX_NUM];
        int dis[MAX_NUM];  // 保存到其他点的距离
        for (int i = 0; i < num; i++)
        {
            if (map[begin][i])  // 设置为原本的距离
            {
                dis[i] = map[begin][i];
                path[i] = begin;
            }
            else    // 不存在就设置距离为无穷大
            {
                dis[i] = INF;
                path[i] = -1;
            }
        }

        // 初始化访问数组全部为未访问
        for (int i = 0; i < num; i++)
            visit[i] = false;
        visit[begin] = true;    // 起始结点已经被访问
        
        // 已经添加了一个begin，还需要将剩下num-1个点加入
        for (int i = 0; i < num - 1; i++)
        {
            int min_index = -1;
            int min_dis = INF;
            // 找到当前最小的一条边
            for (int j = 0; j < num; j++)
            {
                if (min_dis > dis[j] && visit[j] == false)
                {
                    min_dis = dis[j];
                    min_index = j;
                }
            }
            if (min_dis == INF) // 存在最短距离
                continue;

            visit[min_index] = true;    // 该点加入到目标点集中

            // 更新距离
            for (int j = 0; j < num; j++)
            {
                if (map[min_index][j] != 0 && dis[j] > dis[min_index] + map[min_index][j])
                {
                    dis[j] = dis[min_index] + map[min_index][j];
                    path[j] = min_index;
                }
            }

        }

        // 输出路径
        for (int i = 0; i < num; i++)
        {
            if (i == begin) // 到自己的路径不必输出
                continue;
            // 先输出长度和信息
            cout << nodes[i] << " : " << dis[i] << endl;
            // 如果不存在路径
            if (dis[i] == INF)
            {
                cout << "no path!" << endl;
                continue;
            }
            // 使用栈来输出完整路径
            stack<int> s;
            int now = path[i];
            s.push(i);
            while (now != begin && now != -1)
            {
                s.push(now);
                now = path[now];
            }
            s.push(now);

            while (!s.empty())
            {
                cout << nodes[s.top()] << "--->";
                s.pop();
            }
            cout << endl;
        }
    }

​ 最后对$Dijkstra$算法进行一点补充，该算法只能计算边的权重值大于0的情况，对于边权值小于0的一些情况，该算法无法进行正确计算，接下来简单列举两个例子。

​ 能正确进行计算：

​ 不能正确计算：

$Floyd$算法

​ 前面介绍到的$Dijkstra$算法是一个单源算法，也就是只能计算出某个点到其他点的最短距离。而接下来要介绍的$Floyd$算法则是多源算法，即一次性计算出所有点之间相互的最短距离。

​ $Floyd$算法的核心，也就是算法思路，来自于动态规划，故其核心为该表达式。
$$map\left[i\right]\left[j\right]=\min \left(map\left[i\right]\left[j\right],map\left[i\right]\left[k\right]+map\left[k\right]\left[j\right]\right)$$
该公式从直观上也很好理解，$map[i][k]+map[k][j]$也就是$i$通过$k$的中转到达$j$。该算法的正确性验证较为复杂，目前还未找到一个较为正式的证明过程，可以先参考该博客下的内容：

https://blog.csdn.net/ljhandlwt/article/details/52096932?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.control

代码实现十分简单，5行代码足矣，可以当作模板直接使用，如下所示。

// Floyd算法
    void Floyd()
    {
        for (int k = 0; k < num; k++)
        {
            for (int i = 0; i < num; i++)
            {
                for (int j = 0; j < num; j++)
                {
                    if (map[i][j] > map[i][k] + map[k][j])
                    {
                        map[i][j] = map[i][k] + map[k][j];
                    }
                }
            }
        }
    }

最小生成树与最短路径的区别

​ 在对最小生成树和最短路径进行学习和理解之后，接下来需要对这两个概念进行一个综合的区分。

​ 最小生成树能够保证整个拓扑图的所有路径之和最小，但不能保证任意两点之间是最短路径。最短路径是从一点出发，到达目的地的路径最小。

遇到求所有路径之和最小的问题用最小生成树&并查集解决；遇到求两点间最短路径问题的用最短路，即从一个城市到另一个城市最短的路径问题。

​ 最小生成树构成后所有的点都被连通，而最短路只要到达目的地走的是最短的路径即可，与所有的点连不连通没有关系。