我们时常会面临对路径选择问题。例如，在北京、上海、广州等城市，因为城市面积较大，乘地铁或公交从A到B，如何换乘到达？

在现实生活中，每个人需求不同，有人希望时间最短，有人希望换乘少，有人希望花的钱少，简单的图形可以靠人的感觉和经验，复杂的网络就需要计算机通过算法来提供最佳方案。这一节我们就要研究这个问题，即最短路径。

如果将交通网络画成带权图，结点代表地点，边代表城镇间的路，边权表示路的长度，则经常会遇到如下问题：两给定地点间是否有通路？如果有多条通路，哪条路最短？我们还可以根据实际情况给各个边赋以不同含义的值。例如，对司机来说，里程和速度是他们最感兴趣的信息；而对于旅客来说，可能更关心交通费用。有时，还需要考虑交通图的有向性，如航行时顺水和逆水的情况。带权图的最短路径是指两点间的路径中边权和最小的路径。

在网络图和非网络图中，最短路径的含义是不同的。由于非网图没有边上的权值，所谓最短路径，就是指两个顶点之间经过的边数最少的路径；对于网络图来说，最短路径是指两个顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。显然，我们研究网络图更有实际意义。

求最短路径的方法有两种：

（1）求一结点到其他结点的最短路径；

（2）求任意两点间的最短路径。