最短路问题例题

问题：求出A-F之间最短路线；（1）写出思路于算法；（2）Matlab 编程找出最短路径。

答案：A-F之间的最短路线有A-B3-D3-E1-F，A-B3-D3-E1-E2-F；A-B2-C1-D1-D2-E2-F 这三条路线的最短距离均为8。

方案一：思路：对于是否返回的分析：如图可以看出只有B端才能跨越C端的点直接到达D端的，其余的各端点都是必须按照字母顺序一路下来。

若如D端返回到C端或B端这是不可能的，因为这样无疑增加了路程，如图可以看出C端的点能到达D端的各个点，所以要求的直接命中想到达的该点；而D端出发去到E端后有图可以看出不可能再返回D端了，因为这只会增加路线的长度，而且E 端的各点是相通的，也没必要再返回D端；同样B端到达C端或D端的，因为B2,B2到能直接到达C端的各点，只有B1只能到达C1，但B1它到D1的距离和B1点到C1的距离同样为4但也不可能经过C1后返回B端的，因为C1也是联系D端的各点，而且你要返回B 段端，还不如在A端的时候就选择好一个理想的B点，这样距离会更加短。

所以不能进行返回。

如图将我们本来所需要的的路线分成两半，以D字母的为中间端。

后半部分：后半部分主要由D端连接到E端最后才连接到F端的,同时D端无法越过E端直接连接到F端。

更为重要的是前半部分，也必须要经过D端才能与F端相接，所以构成他们之间的枢纽定在D端是最好不过的。

首先的是先分析D端的三个点D1，D2，D3分别到点F的最短距离。

一、已经从D端出发去到E端后有图可以看出不可能再返回D端了，因为这只会增加路线的长度，而且E端的各点是相通的，也没必要再返回D端；二、由图可以看出E端到点F最好的路线是E2-F距离为1，除E2外的E1，E3他们到F点的方式（E1-F, E1-E2-F ,E3-F ,E3-E2-F）的距离均为2；所以如果能先到达E2则可以只考虑E2到F这条路线。

若先到达了E1，或E3、则这路线的最短路径必定变化为两条。

三、由于D3到E端的三条路线D3-E2，D3-E5的距离均为5，与D3-E1的距离为2相差着3的距离点，而即使E2-F的距离是1，比E1,E3到F的距离都少了1的距离点，但依然无法补充3个距离点的差距，对于E3-F就跟不用说了，所以D3连接E1是众望所归的。

所以归纳D3到F的最短路线可为（D3-E1-F, D3-E1-E2-F）距离均为4. 四、面对D2到E端的线路，它可以先经过D1点再过E端的点，但D2点到E2点也只是1的距离，已经是最少了距离线了，更加重要的是E2点到F点的距离也只是1比E1，E3点都要短，所以D2到F的最短线路是(D2-E2-F;)距离为2五、对于D1点到F点的路线，首先可以先看出D1能直接到达E端的E,1，E2两点，但经分析若选择D1直接经过E1点的路径（D1-E1-F或D1-E1-E2-F）但他们的距离长也为4；D1直接经过E2，则由E2到达F点，路径（D1-E2-F）总距离也是为4；但同时别把D1能通过的D2忽视了，经第四点可以知道D2到F的最短距离为2，而D1到D2的距离为1，所以总距离为3，因此D1到F的最短路径为（D1-D2-E2-F）距离为3经上述分析归纳出D端各点到达F的最短路径和距离为D1到F的最短路径为（D1-D2-E2-F）总长度为3、D2到F的最短线路是(D2-E2-F;)总长度为2、D3到F的最短路线可为（D3-E1-F或D3-E1-E2-F）总长度为4、前半部分一、因为C端的点与其他点的联系比较多，所以先找出C端各点到F的最短路径。

1、首先对C1进行分析：C1与D端的各点能直接相连，同时与B端的B1，B2相连，之前已经分析过返回的可能性了，所以C1与F的最短路径必定是直接链接到D端的点。

由于C1-D1的距离为2，C1-D2的距离为5，C1-D3的距离为3，再联系上述的“D1到F的最短路径为（D1-D2-E2-F）总长度为3、D2到F的最短线路是(D2-E2-F;)总长度为2、D3到F的最短路线可为（D3-E1-F或D3-E1-E2-F）总长度为4、”所以可以明确地找出C1到F的最短路径（C1- D1-D2-E2-F）总长度为5。

2、对于C2来说，理由也与C1的基本相同，分析：C2-D1的距离为1，C2-D2的距离为4，C2-D3的距离为2，同时也根据“D1到F的最短路径为（D1-D2-E2-F）总长度为3、D2到F的最短线路是(D2-E2-F;)总长度为2、D3到F的最短路线可为（D3-E1-F或D3-E1-E2-F）总长度为4、”所以也可以精确地找出C2到F的最短路径为（C2-D1-D2-E2-F）总长度为4。

二、再进一步的就是对B端的各点进行分析了，1、先对B1进行分析，B1到达F端的的路线可以选择与C1或D1相连接，但“D1到F的最短路径为（D1-D2-E2-F）总长度为3、C1到F的最短路径（C1- D1-D2-E2-F）总长度为5”而B1距离D1或距离C1的长度均为4，所以可以分析出B1到达F的最短路径为（B1-D1-D2-E2-F）总长度为7。

2、再次是对B2点进行到达F的点进行比较了，与B2 的前方相连的就只有C1和C2了，而B2-C1的距离为1，B2-C2的距离为3，并且“C1到F的最短路径（C1- D1-D2-E2-F）总长度为5、C2到F的最短路径为（C2-D1-D2-E2-F）总长度为4、”所以综合上述的情况可以比较出：B2到达F的最短路径为（B2-C1- D1-D2-E2-F）总长度为6。

3、最后是对B3到F点的长度的比较，与B3的前方相连接的有点C1、C2、D3三个点，路径B3-C1的距离为3，B3-C2的路径为5,B3-D3的路径为3，同时“C1到F的最短路径（C1- D1-D2-E2-F）总长度为5、C2到F的最短路径为（C2-D1-D2-E2-F）总长度为4、D3到F的最短路线可为（D3-E1-F或D3-E1-E2-F）总长度为4、”因此经综合分析B3到达F最短的路径为（B3-D3-E1-F或B3-D3-E1-E2-F）总长度为7。

三、到最后的一个A点与B端的相连接了，为分析出A到达F端的最短路径，分别列出B端各点到达F点的最短路径为“B1到达F的最短路径为（B1- D1-D2-E2-F）总长度为7、B2到达F的最短路径为（B2-C1- D1-D2-E2-F）总长度为6、B3到达F最短的路径为（B3-D3-E1-F或B3-D3-E1-E2-F）总长度为7、”同时也因为路径A-B1的距离为3，A-B2的距离为2，A-B3的距离为1，所以与综上的B端到达F点的最短距离比较可以得出:A端到达F点的最短路径为：（A-B2-C1- D1-D2-E2-F）（A-B3-D3-E1-F）（A-B3-D3-E1-E2-F）这三条A-F的路径均为A-F的最短路径，最短路径长度为8。

方案二：对于是否返回的分析：如图可以看出只有B端才能跨越C端的点直接到达D端的，其余的各端点都是必须按照字母顺序一路下来。

若如D端返回到C端或B端这是不可能的，因为这样无疑增加了路程，如图可以看出C端的点能到达D端的各个点，所以要求的直接命中想到达的该点；而D端出发去到E端后有图可以看出不可能再返回D端了，因为这只会增加路线的长度，而且E 端的各点是相通的，也没必要再返回D端；同样B端到达C端或D端的，因为B2,B2到能直接到达C端的各点，只有B1只能到达C1，但B1它到D1的距离和B1点到C1的距离同样为4但也不可能经过C1后返回B端的，因为C1也是联系D端的各点，而且你要返回B 段端，还不如在A端的时候就选择好一个理想的B点，这样距离会更加短。

所以不能进行返回。

首先能找出一条从A点通向F点的路径，一、在不返回的情况下，找出该点到下一个点的距离为最短的路径，然后如此延续下去直到到达F点；1、从A点开始进行比较，可得出的路径为（A-B3-C1-D1-D2-E2-F）和（A-B3-D3-E1-E2-F）；如下图所示：2、经过计算路径（A-B3-C1-D1-D2-E2-F）的总长度为9，而（A-B3-D3-E1-E2-F）的总长度为8。

二、1、让A先到达B2该点，然后按照（一）说的步骤延续下去可以得出路径为（A-B2-C1-D1-D2-E2-F），如下图所示：2、经过计算路径（A-B2-C1-D1-D2-E2-F）的总长度为8，三、1、让A先到达B1该点，然后按照（一）说的步骤延续下去可以得出路径为（A-B1-C1-D1-D2-E2-F）和(A-B1-D1-D2-E2-F)，如下图所示：2、经过计算路径（A-B1-C1-D1-D2-E2-F）的总长度为12，而（(A-B1-D1-D2-E2-F）的总长度为10。

四、经过比较目前的最短路径有两条，分别为“（A-B3-D3-E1-E2-F）的总长度为8、（A-B2-C1-D1-D2-E2-F）的总长度为8、”五、对以上两条线路被认为最短进行分析和比较:1、首先针对（A-B2-C1-D1-D2-E2-F）的总长度为8进行分析：它的轨迹正如下图所示：因为A-B2是先被确定下来的，所以不从这方面进行解释，但由B2到达F点都是必须按照字母顺序一路下来才能到达F点的，而且B2点向前直接连接的点只有C1、C2这两个点、同时按照其余个线路的长度和曲线问题来分析。

（1）选择C1作为B2的连接点，已经是以1的距离连接的了，在这各两点的距离中没有比1更小的距离点了，即系是经过B3再到达C1，那么路径则为（A-B3-C1）总长度为4，比路径（A-B1-C1）的总长度多1；所以C1作为B2的连接点是好无疑问的。

（2）而选择D1作为B2的第二个连接点，是因为B2必须要进过C端才能到达D端的各点，而B2到达C2端的距离点就已经是3了，即使是由路径（A-B1-D1）它的总长度已经是7了，比路径（A-B2-C1-D1）要长；所以选择D1作为第二个连接点也是必须的。

（3）再次选择D2该点作为第三个连接点，主要是因为D1到达F点,中途经过的D2，再由D2经过的E2和E2到达的F点的距离都是1,为最短距离点，而且由于路径（D1-E2）和(D1-E1-E2)的距离是相同的均为3，而且E端到达F点最近的是(E2-F)了，所以从D1点是否能经过E1点来分析来看是不能经过E1点的。

再从是否能经过C2点到达D2或E2，和F点分析来看，若B2点先经过C2点再到达D2点的说法，可以从该处的距离看出路径（B2-C2-D2）的距离为7，而路径（B2-C1-D1-D2）的路径为4，所以若B2经过C2再到达D2的这个说法可以直接被排除；那么C2若不经过D2与E2进行连接的话，就要经过D3该点了，则路径为（B2-C2-D3-E2）总长度为10，或（B2-C2-D3-E1-E2）总长度为8，于原本的总线路（A-B2-C1-D1-D2-E2-F）的总长度未8的相比，显然这已经是不可能的了；而C2不通过D2、E2直接到达F点的方法是否可行？在C2点经过D3是必要的，而且它可以选择的路径有（B2-C2-D3-E1-F）总长度为9和（B2-C2-D3-E3-F）总长度为12，均比路径（B2-C1-D1-D2-E2-F）的要长，所以在A点必须经过B2点的情况下，剩下来的就只有（A-B2-C1-D1-D2-E2-F）这条路径是最短的，总长度未8。