標(biāo)號(hào)法求最短路徑例題詳解

關(guān)于標(biāo)號(hào)法求最短路徑例題詳解2標(biāo)號(hào)法(E.W.Dijkstra,1959)設(shè)帶權(quán)圖G=<V,E,w>,其中

e

E,w(e)0.設(shè)V={v1,v2,,vn},求v1到其余各頂點(diǎn)的最短路徑p標(biāo)號(hào)(永久性標(biāo)號(hào)):第r步獲得的v1到vi最短路徑的權(quán)t標(biāo)號(hào)(臨時(shí)性標(biāo)號(hào)):第r步獲得的v1經(jīng)過(guò)p標(biāo)號(hào)頂點(diǎn)到達(dá)vi的路徑的最小權(quán),是v1到vi的最短路徑的權(quán)的上界第r步通過(guò)集Pr={v|v在第r步已獲得永久性標(biāo)號(hào)}第r步未通過(guò)集Tr=V-Pr第2頁(yè),共10頁(yè)，2024年2月25日，星期天3標(biāo)號(hào)法(續(xù))1.v1獲p標(biāo)號(hào):=0,P0={v1},T0=V-{v1},vj(j=2,3,,n)獲t標(biāo)號(hào):=wij.令r1.2.設(shè),vi獲得p標(biāo)號(hào):.

令Pr=Pr-1{vi},Tr=Tr-1-{vi}.

若Tr=,則結(jié)束.3.vj

Tr,令令r=r+1,轉(zhuǎn)2.算法:第3頁(yè),共10頁(yè)，2024年2月25日，星期天4標(biāo)號(hào)法求最短路徑

第一步：

標(biāo)號(hào)法求v0到v5的最短路徑

v0

v1

v2

v3

v4

v5

0014

vir因?yàn)榈谝徊絭0只能夠到達(dá)v1和v2，所以v1和v2下面寫(xiě)到達(dá)的權(quán)重，而v3~v5寫(xiě)無(wú)窮大。第4頁(yè),共10頁(yè)，2024年2月25日，星期天5標(biāo)號(hào)法求最短路徑

第二步：

標(biāo)號(hào)法求v0到v5的最短路徑

v0

v1

v2

v3

v4

v5

0014

11/v0386

vir因?yàn)榈谝徊降玫降臄?shù)字當(dāng)中除了已經(jīng)確定的0以外，1最小，所以到達(dá)v1的最短路徑確定了，為1，并且通過(guò)v0。因?yàn)橥ㄟ^(guò)v1到達(dá)v2需要3步，比4小，所以v2處寫(xiě)3。同理，因?yàn)橥ㄟ^(guò)v1到達(dá)v3和v4的權(quán)重和小于正無(wú)窮。第5頁(yè),共10頁(yè)，2024年2月25日，星期天6標(biāo)號(hào)法求最短路徑

第三步：

標(biāo)號(hào)法求v0到v5的最短路徑

v0

v1

v2

v3

v4

v5

0014

11/v0386

23/v08

4

vir因?yàn)榈诙降玫降臄?shù)字當(dāng)中3最小，v2最短為3。因?yàn)橥ㄟ^(guò)v2不能直接到達(dá)v3，所以v3下面還是8。通過(guò)v2到達(dá)v4需要4到達(dá)不了v5第6頁(yè),共10頁(yè)，2024年2月25日，星期天7標(biāo)號(hào)法求最短路徑

第四步：

標(biāo)號(hào)法求v0到v5的最短路徑

v0

v1

v2

v3

v4

v5

0014

11/v0386

23/v08

4

3

74/v210vir第7頁(yè),共10頁(yè)，2024年2月25日，星期天8標(biāo)號(hào)法求最短路徑

第五步：

標(biāo)號(hào)法求v0到v5的最短路徑

v0

v1

v2

v3

v4

v5

0014

11/v0386

23/v08

4

3

74/v210

47/v49vir第8頁(yè),共10頁(yè)，2024年2月25日，星期天9

v0

v1

v2

v3

v4

v5

0014

11/v0486

24/v08

5

385/v26486/v4

58/v1

w014856

=