【图论2-2】最短路

最短路是图论中最经典的模型之一，在生活中也有很多应用。举个例子，我国幅员辽阔，有 很多个城市。这些城市之间由许多高速公路相连接。想从上海出发前往北京，有很多种路径，如 何选择一条最短的路径就是最基本的最短路问题。有时候问题会更加复杂，加上别的限制条件， 例如某些城市拥有服务区，连续开车达到一定的时间就必须要进服务区休息，或者是某些路段在 特定的时间内会堵车，需要绕行等等，这需要更加灵活地使用最短路算法来解决这些问题。 除了解决给定图的最短路问题，最短路模型还可以解决许多看起来不是图的问题。如果解决 一个问题的最佳方案的过程中涉及很多状态，这些状态是明确的且数量合适，而且状态之间可以 转移，可以考虑建立图论模型，使用最短路算法求解。本章介绍了多种适用于不同情况的最短路 算法，可以根据实际情况选择合适的算法。 该题单内容将继续改进。 对应进阶篇第 10 章。