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

2024-01-03 13:33:13

对如下有向带权图,若采用迪杰斯特拉(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}

文章来源:https://blog.csdn.net/weixin_45528773/article/details/135359791
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。