dijkstra的基本想法是，为了找到S(ource)到T(arget)的最短路径，先找离S最近的点x1，然后找离S第二近的点x2，不停地循环下去，直到某一次找到的就是T，那么就找到了S到T的最短路。因为每次选择的初衷都是尽可能地找离得近的点，而压根不考虑会不会快速找到T，所以实际上dijkstra每趟都是找到了一条S和某个点之间的最短路。进而，算法的正确性显而易见。

为了实现这个算法，具体编程的时候实际上相当于维护了一个frontier。通俗地说，这个frontier就是截至到目前为止，我能到的最远的地方有那些。所谓“能到”，是指排除掉那些距离仍为无穷的点；所谓“最远”，是指排除掉已经找到最短路的点。有了这个定义以后，dijkstra算法每一趟循环要做的，其实就是从frontier中找到离S最近的点，标记为“已经找到最短路”，把这个点从frontier中删除，再把这个点的所有出边放松，以纳入新的frontier。

具体而言，最开始，我能到的地方只有S，其他点都是无穷。于是把S从frontier中删去，同时把S出边的另一个端点放进frontier；第二趟循环，把当前frontier中离S最近的点删去，同时把跟它临接的点放进frontier（如果已经在frontier里面的话，则在必要的时候进行更新即可）；以此类推。

把这个方法扩展到bi-direction，自然的想法是从S找最近的点，比如依次是x1、x2、…，统统放进集合X。从T也找最近的点，依次是y1、y2，…，放进集合Y。如果某一趟找到的x在Y里已经出现过了，或者y在X里已经出现过了，则找到了最短路径。为什么？假定这个重合的点叫做U，那么S到U的最短路径和U到T的最短路径都找到了，连接起来就是S到T的最短路。

但这个思路有个问题：万一S到T的最短路实际上不经过U怎么办？我们直到，如果S到T的最短路径经过U，那么SU、UT也一定都是最短路。可是反过来却不一定成立，比如S-U-T，SU、UT都是2，ST之间再来一条直接相连的长度为3的边。上面的方法找到的最短路是SUT，但显然是不对的。

那么，bi-direction dijkstra怎么才能正确地找到两个点之间的最短路径呢？首先，至少两个frontier要有交集，不然根本就连一条路径都还没找到。但是光是frontier相交还不够：想象S和T之间有一条直接相连的边，只不过长度是正无穷。那么在第一次循环的时候这条边就被放松了，S和T的frontier就已经相交了，但是最短路压根就还没出现。

比frontier相交强一步，是XY相交，也就是前面提到的方法。可是这也不够，刚刚已经分析过了。能不能对这个方法做一些改进呢？要想回答这个问题，我们首先要弄清楚，XY相交的时候最短路有没有出现。要是像上一种情况一样，最短路有可能还没出现的话，任何想改进的努力都注定是白费功夫。

所谓最短路没出现，就是说ST之间的最短路现在还没连通。注意，ST可能是连通的，但是ST之间的最短路没有连通。换言之，这条最短路径上至少有一条边还没被放松。假定这条边是AB，那么现在最多就是SA被连通、BT被连通，SB、AT都还是正无穷。这种情况有没有可能呢？

幸运的是，答案是否定的。因为如果真的没连通，那么SABT这条路径决不可能是最短路。为什么？考虑边AB，AB未被放松过，这意味着A、B两个点最多处在frontier上，还没被标记为“已经找到最短路”（否则AB这条边就已经被放松过了）。又考虑到X和Y已经产生了交集，假定相交与点U，那么根据dijkstra的思路，SU的距离一定小于等于SA的距离，同理UT的距离一定小于等于BT的距离。注意到SABT这条路线还要经过边AB，可以得出路径SUT一定比SABT短，所以SABT不是最短路径。

毫无疑问，这是个振奋人心的消息，因为我们至少可以确定，在XY相交的时候，最短路径已经连通了，只是可能还没有被我们识别出来而已。什么叫识别，什么叫没识别？识别出来的，就是一个个的x、y，组成了集合X、Y。没识别出来的，就是两个frontier里面的点——他们已经被连通了，可是还没被确定为“已经找到最短路”的点。弄明白这个问题就好办了，我们只要把两个frontier中所有的点和U进行比较就行了：找到点V，使得SV+VT最小，那么SVT就是S、T之间的最短路径。

PS：原来在WP中插图是这么麻烦的。。。