综合题
如图 3 所示， A 处有 M 个城市， B 处有 N 个城市， A， B 之间有一些城市， A， B 及其之间所有的城市构成了一个图， 图的信息已经全部存储在邻接矩阵存储结构中， 问如何从 A 处选择一个城市 a， 从 B 处选择一个城市 b， 使得由 a 到 b 的路径最短。 要求给出 a， b 的选择和求出 a， b 间最短路径长度的方法描述， 无需写代码，只描述解决办法即可（迪杰斯特拉或者弗洛伊德算法可以直接选用）。
【正确答案】
一种可行的解决办法为： 在图的存储结构中添加两个顶点信息， 一个为起点一个为终点， 如图 3 所示。
使得起点到 A 处所有城市都有路径相通， B 处所有城市到终点都有路径相通， 并使得新添加的路径长度均为固定值 L。
选用迪杰斯特拉算法求从起点到图中其余各点的最短路径（当然包括终点）。 从最后所得的最短路径数组中可以查出从起点到终点的最短路径上的顶点序列， 则序列中第二个顶点即为所找的 a， 倒数第二个顶点即为所找的 b； 从最短路径长度数组中可以查出由起点到终点的最短路径长度值为 S， 则 S-2L 即为从 a 到 b 的最短路径长度。
【答案解析】