最短路径问题是最广为人知的图论问题，在详细展开各种最短路径算法之前，先说明几个关键概念和问题。
1. 最短路径问题
一个图中有 n 个点和 m 条边。边有权值，权值可正可负。边可能是有向的，也可能是无向的。给定起点 s 和终点 t，在所有连接 s 和 t 的路径中，寻找边的权值之和最小的路径，这就是最短路径问题。
2. 可加性参数和最小性参数
这两种参数区分了最短路径问题和网络流问题。
最短路径是计算“路径上边的权值之和”。边的权值是“可加性参数”，如费用、长度等，它们是“可加的”，一条路径上的总权值是这条路径上所有边的权值之和。
最小生成树问题中，边的权值也是“可加性参数”。
在网络流问题中，是找“路径上权值最小的边”，如最大流问题，边的权值是“最小性参数”。例如水流，一条路径上能流过的水流取决于这条路径上容量最小的那条边。再如网络的带宽，一条网络路径上的整体带宽是这条路径上带宽最小的那条边的带宽。
3. 用DFS搜索所有路径
在一般的图中求任意两点间的最短路径，首先需要遍历所有可能经过的节点和边，不能有遗漏；其次，在所有可能的路径中查找最短的一条。如果用暴力法查找所有路径，最简单的方法是把 n 个节点进行全排列，然后从中找到最短的。但是共有 n! 个排列，这是一个天文数字，无法求解。
更好的办法是用DFS输出所有存在的路径，这显然比 n! 要少得多，不过复杂度仍然是指数级的，所以，最短路径的求解，不能先求出所有路径然后再从中找出最短路的，而是需要在遍历节点和边的过程中动态寻找最短路径，这就是各种最短路径算法需要解决的问题。
4. 用BFS求最短路径
在特殊的图中，所有边都是无权的，可以把每条边的长度都设为 1 ，此时BFS是很好的最短路径算法。
5. 不同的应用场景
有多种最短路径的应用场景，它们需要用不同的算法来解决。下表总结了一些经典算法，除了贪心最优搜索之外，其他都是最优性算法，即得到的解是最短路径。其中 m 是边的数量，n 是点的数量。
