最短路径问题总结介绍

摘要：最短路问题是图论中一个经典的问题，也是优化问题中能被有效求解的一类问题，无论是城市交通、通信路由还是芯片的表面设计，找到最短路径都具有现实意义。

1. 最短路径问题的分类

（1）一个起点多个终点的最短路径问题

        （1.1）含负权，也就是有些边的权重为负值；

       （1.2）不含负权，也就是所有边的权重不为负值；

        （1.3）含环路，可以由某一起点始发经过相位路径后回到起点；

        （1.4）不含环路，任意节点都不能经某条路径回到改点；

（2）多个起点多个终点的最短路径问题

       （2.1）含负权，也就是有些边的权重为负值；

       （2.2）不含负权，也就是所有边的权重不为负值；

        （2.3）含环路，可以由某一起点始发经过相位路径后回到起点；

        （2.4）不含环路，任意节点都不能经某条路径回到改点；

1. 最短路问题的算法

最优性算法原理：在一个没有负权环路的图中，最优路径一定包含着最优子路径（最优性原理）

有了上述最优性原理，可以知道，解决最短路径问题的算法一定是从动态规划的角度出发，虽然线性规划也可以解决最短路径问题，但是有文献证明，相比之下，使用最优性原理的动态规划算法效率更高。

2.1  Bellman-ford算法

该算法是典型的动态规划算法，主要解决的是一个起点多个终点的最短路径问题，注意该方法能够解决所有一个起点多个终点的最短路径问题（包括是否含负权以及是否含环路），但是效率并不是最高的，具体算法的链接见：

https://www.cnblogs.com/gaochundong/p/bellman_ford_algorithm.html

2.2 Djikstra算法

该算法是非常经典和被广泛应用的寻找最短路径的算法，它主要解决的是一个起点多个终点的最短路径问题，且所有的边都不含负权。相比于Bellman-ford算法的复杂度O(n^3)，Djikstra算法的复杂度为O(n^2),算法的具体介绍见：

https://zhuanlan.zhihu.com/p/40338107

2.3 A*算法

 A*算法是最近比较流行的一种算法，它是Djisktra算法的拓展，针对的问题类型是同样的，在评价最短路径的时候启发式地增加了一个评价中间节点到终点代价的函数，其余的算法思路同Djisktra算法都是一样的。   具体的对比与介绍见：

https://zhuanlan.zhihu.com/p/54510444     

2.4  普通动态规划算法

      普通的动态规划算法针对的问题是不含环路的一个起点多个终点的最短路径问题。

2.5 Floyd-Warshall算法：

该算法也是典型的动态规划算法，针对的问题是多起点多终点的最短路径问题。其实，有了Bellman-Ford算法很自然地，就会想到在该算法的基础上再遍历一遍所有的路口，似乎就能够解决多起点多终点的最短路径问题，但是，这种做法不够聪明，于是就有了Floyd-Warshall算法，具体该算法介绍见链接：

https://blog.csdn.net/qq_35644234/article/details/60875818

综上，最短路径问题最重要的是要找到问题的分类，然后再根据问题的分类去寻找对应最有效的算法。另外，最长路径问题和最短路径问题刚好是min-max的关系，只需要作相应的min-max变化就可以了，但是由于最长路径问题中往往含有正权环路，所以很多时候不能被有效解决，对于无环路的情况，就不会受到限制，也可以通过对边权重的倒数转换等方式把最长路径问题转换成最短路径问题。