最短路问题;short-path problem

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

单源最短路径问题

——包括确定起点的最短路径问题，确定终点的最短路径问题（与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。） 算法可以采用Dijkstra算法。

确定起点终点的最短路径问题

——即已知起点和终点，求两结点之间的最短路径。

全局最短路径问题

——求图中所有的最短路径。算法可以采用Floyd-Warshall算法。如果图中有负权回路，可以采用Bellman-Ford算法