从有向带权图判断最短路径里各目标顶点顺序

对如下有向带权图，若采用迪杰斯特拉(Dijkstra)算法求从源点a到其他各顶点的最短路径，则得到的第一路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是()

A.d,e,f

B.e,d,f

C.f,d,e

D.f,e,d

首先，先看除了a还有5个顶点，那么就是要走5趟。

在下面表格列出b、c、d、e、f 以及一两三四五趟，最后一行写集合。

顶点	一趟	两趟	三趟	四趟	五趟
b
c
d
e
f
集合

---

1. 在一开始我自己定义：
   1. 顶点a至b算一趟，顶点a至c也算一趟
   2. 以此类推，例如后面讲述的顶点a至b至c算两趟
2. 然后再看，从a出发，首先接触的是b、c，那么分别写下到b和c的距离。
3. 其他顶点对a来说一趟接触不到，那么我们就写无穷，即∞。
4. 其中，(a,b)最短，距离为2，那么得出结论：集合就是{a，b}
5. 由于顶点c这次没被引用，于是将(a,c)5先搁置至二趟（但每一次搁置到后面一趟需检验a至c是不是最短的，还有没有从a至c更加短的距离，详情看后面几轮）

顶点	一趟	两趟	三趟	四趟	五趟
b	(a,b)2
c	(a,c)5	(a,c)5
d	∞
e	∞
f	∞
集合	{a，b}

---

1. 然后再看，从a至b出发，能走两趟的就只有(a,b,c)和(a,b,d)，此时(a,b,c)距离为3，(a,b,d)距离为5。
2. 上一趟的(a,c)搁置到二趟需检验a至c是不是最短的，还有没有从a至c更加短的路线，哦有，就是我们刚才写的(a,b,c)，(a,c)距离为5，(a,b,c)距离才3，那么就用(a,b,c)代替(a,c)。
3. 此时(a,b,c)距离为3，(a,b,d)距离为5
4. 那么最短的就是(a,b,c)
5. 那么集合就是{a，b，c}

顶点	一趟	两趟	三趟	四趟	五趟
b	(a,b)2
c	(a,c)5	(a,c)5/(a,b,c)3
d	∞	(a,b,d)5
e	∞	∞
f	∞	∞
集合	{a，b}	{a，b，c}

---

 

1. 然后再看，此时b和c都被引用了，就剩d、e、f，即从a至b至c出发，能走三趟的，能接触到的就是d、e、f
2. 此时三趟为(a,b,c,d)距离为6，(a,b,c,e)距离为7，(a,b,c,f)距离为4。
3. (a,b,d)因为上一趟距离长没有选上，虽不是最短，但可以先搁置到这一趟继续写，但搁置到这一趟需检验a至d是不是最短的，还有没有从a至d更加短的路线，哦没有，还是(a,b,d)，(a,b,c,d)距离为6，(a,b,d)距离才5，那么就保留(a,b,d)。
4. 此时三趟为(a,b,d)距离为5，(a,b,c,e)距离为7，(a,b,c,f)距离为4，(a,b,c,f)最短，选(a,b,c,f)。
5. 故集合为｛a，b，c，f｝

顶点	一趟	两趟	三趟	四趟	五趟
b	(a,b)2
c	(a,c)5	(a,c)5/(a,b,c)3
d	∞	(a,b,d)5	(a,b,d)5/(a,b,c,d)6
e	∞	∞	(a,b,c,e)7
f	∞	∞	(a,b,c,f)4
集合	{a，b}	{a，b，c}	｛a，b，c，f｝

---

  

1. 然后再看，从a至b至c至f出发，能走四趟的，能接触到的就是d、e
2. (a,b,d)是从二趟开始搁置到这一趟，因为已经检验过了所以不用检验，而(a,b,c,e)是从三趟才开始搁置的，还没检验过，检验一下，(a,b,c,e)距离为7，(a,b,d,e)距离为6，(a,c,e)距离为9，(a,b,c,d,e)距离为7，故(a,b,d,e)最短，用(a,b,d,e)替代这几个
3. 然而虽然(a,b,d,e)距离为6，(a,b,d)5距离为5而已，故还是选(a,b,d)。
4. 故集合为｛a，b，c，f，d｝

顶点	一趟	两趟	三趟	四趟	五趟
b	(a,b)2
c	(a,c)5	(a,c)5/(a,b,c)3
d	∞	(a,b,d)5	(a,b,d)5/(a,b,c,d)6	(a,b,d)5
e	∞	∞	(a,b,c,e)7	(a,b,c,e)7/(a,b,d,e)6/(a,c,e)9/(a,b,c,d,e)7
f	∞	∞	(a,b,c,f)4
集合	{a，b}	{a，b，c}	｛a，b，c，f｝	｛a，b，c，f，d｝

---

 

1. 然后再看，此时就剩e，即从a至b至c至f至d出发，能走五趟的，能接触到的就只有e了
2. (a,b,d,e)是从四趟开始搁置到这一趟，因为已经检验过了所以不用检验。
3. 故集合为｛a，b，c，f，d，e｝

顶点	一趟	两趟	三趟	四趟	五趟
b	(a,b)2
c	(a,c)5	(a,c)5/(a,b,c)3
d	∞	(a,b,d)5	(a,b,d)5/(a,b,c,d)6	(a,b,d)5
e	∞	∞	(a,b,c,e)7	(a,b,c,e)7/(a,b,d,e)6/(a,c,e)9/(a,b,c,d,e)7	(a,b,d,e)6
f	∞	∞	(a,b,c,f)4
集合	{a，b}	{a，b，c}	｛a，b，c，f｝	｛a，b，c，f，d｝	｛a，b，c，f，d，e｝

故后续得到的其余各最短路径的目标顶点依次是｛a，b，c，f，d，e｝