3.3.3 寻找最短路径的方法
现在，原来的问题已经变为运筹学中一个单纯的图论问题，即寻找图3-9中从A点到F点之间的最短路径。应如何寻找从A点到F点的最短路径呢？
对于这个问题，常用的方法有两种，一是枚举法，也就是枚举出两点之间的每一条路线，然后比较这些路线的长度，从中找出长度最短的；二是运筹学中的迪杰斯特拉算法，比枚举法效率更高，能够帮助我们更快地找到两点之间的最短路径。
方法一 ：枚举法
找出从A点到F点的每条路线，再比较各自的长度，选择长度最短的那条。根据图3-9可以发现，从A到F的路线分为两种情况：
（1）从A到B，再经过其他点到F；这时可以得到从A点到F点的路线有以下四条，并且能够得到各条路线的长度。
A—B—D—F，长度是55；
A—B—C—D—F，长度是50；
A—B—C—F，长度是55；
A—B—C—E—F，长度是60。
（2）从A到C，再经过其他点到F；这时可以得到从A点到F点的路线有以下三条，并且能够得到各条路线的长度。
A—C—D—F，长度是55；
A—C—F，长度是60；
A—C—E—F，长度是65。
再比较以上这些路线的各自长度，可以发现，长度最短的路线是A—B—C—D—F，长度是50。再回到原来的实际问题中便可以得到，这批快递的运输路线应从中转站（A点）出发，依次经过B、C和D三个快递站，最后达到目的站（F点），这条路线的距离是50千米，这时运输时间最短。
方法二 ：迪杰斯特拉算法
迪杰斯特拉算法是一种层层推进的方法，能帮助我们避免枚举法中许多不可能是最短路径的情况。
例如，在枚举时可以发现，A—B—C—D—F（长度是50）和A—C—D—F（长度是55）这两条路线中，前者比后者要长，这也就说明后者不再可能是从A点到F点的最短路径了。细究原因，便可以发现在这两路线中，A—B—C的长度比A—C的长度小5，也就是从A到B再到C的长度比从A直接到C更短。进一步来说，可以得到所有包含A—C的线路都不可能是最短路径，例如，A—C—F不可能是最短路径，A—B—C—F也不可能等。
同样，A—B—C也是从A点到C点的最短路径，而A—C却不是。因此，可以得出如果这条线路不是其起点到终点的最短路径，那么包含这条线路的其他线路就不可能是最短线路。例如，A—C不是从其起点（A点）到终点（C点）的最短路径，因此，A—C—F、A—C—E—F、A—C—D—F都不可能是从A点到F点的最短路径。
再来看从A点到B点再经过其他点到F点的四条路线，可以发现，它们的不同点在于从B点到F点的路线不同，各自的路线和长度依次是：B—D—F，长度是40；B—C—D—F，长度是35；B—C—F，长度是40；B—C—E—F，长度是45。从这里也可以看出，从B点到F点的最短路径是B—C—D—F，长度是35。而这条线路也包含在从A点到F点的最短路径A—B—C—D—F中。
总结起来，可以得出一条最短路径往往是由一段段的最短路径组成。例如，A—B—C—D—F这条从A点到F点的最短路径中，其中任何一小段路线都是其起点到终点的最短路径。对于那些不在最短路径之中的连线，也不可能包含在其他的最短路径中。例如A—C，不包含在最短路径A—B—C中，那么A—B也就不可能包含在从A点到F点的最短路径中。
因此，在求从起点到距离较远的终点的最短路径时，可以先求出从起点到较近点的最短路径，逐步进行拓展，得到从起点到较远的点的最短路径，直到找到从起点到终点的最短路径为止。对于那些已经发现的不包含在最短路径中的线路，将其从图中删去，这样即可将问题不断简化。
根据迪杰斯特拉算法，可先从最近的B点开始，逐步寻找从A点到每个点的最短路径：
对于B点，从图3-9中可以看出，从A点到B点只有一条路线，即A—B，因此，A—B就是从A点到B点的最短路径，长度是15，如图3-10所示。
图3-10 从A到B的最短路径A—B
对于C点，从图3-10中可以看出，从A点到C点共有两条路径：A—C，长度是30；A—B—C，长度是25。比较可以得到从A点到C点的最短路径是A—B—C，长度是25。由于A—C不在最短路径中，因此，可以将A—C这条线从图3-10中删去，得到图3-11。
图3-11 从A到C的最短路径A—B—C
对于D点，从图3-11中可以看出，这时A—C已经删去，从A点到D点共有两条路线：A—B—C—D，长度是35；A—B—D，长度是40。比较后得到从A点到D点的最短路径是A—B—C—D，长度是35。由于A—B—D不是最短路径，B—D这条线不在最短路径之中，因此，可以将B—D这条线从图3-11中删去，得到图3-12。
图3-12 从A到D的最短路径A—B—C—D
对于E点，从图3-12中可以看出，这时B—D也已经删去，从A点到E点已经只有一条路径，即A—B—C—E，长度是40。因此，从A到E的最短路径就是A—B—C—E，长度是40。
对于F点，从图3-12中可以看出，从A点到F点共有三条路线：A—B—C—D—F，长度是50；A—B—C—F，长度是55；A—B—C—E—F，长度是60。比较后得到从A点到F点的最短路径是A—B—C—D—F，长度是50。
再回到原来的实际运输问题中，得到最短运输线路就是从中转站（A点），依次经过B、C、D这三个快递站，最后到达目的站（F点），这条路线的距离是千米，运输所用的时间最短。
比较上述两种方法，可以发现，最后求得的最短路径结果是一样的。但是，迪杰斯特拉算法能够大大减少计算的次数，是因为在计算过程中，不断地将不在最短路径之中的连线删去，让图形变得越来越简单，需要考虑的情形也变得越来越少。