最短路问题（short-path problem）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。

单源最短路径

包括确定起点的最短路径问题，确定终点的最短路径问题（与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。） 。求解单源最短路径问题可以采用Dijkstra算法，时间复杂度为O(|V|^2)。Dijkstra算法可以使用斐波那契堆、配对堆等支持Decrease-Key操作的数据结构来进一步优化，优化后的时间复杂度为O(|E|+|V|log|V|)。

全局最短路径

求图中所有的最短路径可以采用Floyd-Warshall算法，算法时间复杂度为O(|V|^3)。如果图中有负权回路，可以采用Bellman-Ford算法，算法复杂度是O(|V||E|)。但Bellman-ford算法浪费了许多时间做无必要的松弛，可用SPFA算法进行优化，SPFA算法是用队列进行的优化，优化后时间复杂度为O(k|E|)，其中k为所有顶点进队的平均次数，可以证明k一般小于等于2，由此可见该优化的效果十分显着。

两点最短路径

即已知起点和终点，求两结点之间的最短路径。通常可以用广度优先搜索（BFS）、深度优先搜索（DFS）等方式来实现，时间复杂度是O(|V|)。

参考资料