15.某景區(qū)共有9個景點(diǎn)(編號依次為0-8),景點(diǎn)之間的連通情況如圖所示,兩個景點(diǎn)之間的數(shù)值表示兩個景點(diǎn)之間的距離。小明想從編號為start的景點(diǎn)盡快到達(dá)編號為end的景點(diǎn)與同學(xué)匯合,小明應(yīng)如何規(guī)劃行進(jìn)路線,使得行走的距離最短?并輸出從起點(diǎn)到終點(diǎn)經(jīng)歷的景點(diǎn)編號。
算法思想:
1將起點(diǎn)到起點(diǎn)的距離設(shè)置為0,起點(diǎn)到其他景點(diǎn)的距離設(shè)置為無窮大
2從未標(biāo)記的景點(diǎn)中選擇距離起點(diǎn)最近的景點(diǎn)A,做標(biāo)記,并收錄到最優(yōu)路徑中
3計(jì)算與景點(diǎn)A相連的景點(diǎn)B的距離:(景點(diǎn)B的距離是指從起點(diǎn)到景點(diǎn)B的距離)
若景點(diǎn)A的距離+景點(diǎn)A到景點(diǎn)B的距離<景點(diǎn)B的距離,更新景點(diǎn)B的距離,并將景點(diǎn)A設(shè)置為景點(diǎn)B前驅(qū)景。
編寫Python程序,實(shí)現(xiàn)上述功能,程序運(yùn)行界面如圖所示。
(1)若景點(diǎn)3到景點(diǎn)4之間的距離為1,則從起點(diǎn)0到終點(diǎn)4的最短距離是
。
(2)定義如下dijkstra(s)函數(shù),參數(shù)s表示起點(diǎn)編號。函數(shù)的功能是求解各個景點(diǎn)距離起點(diǎn)景點(diǎn)的最短距離。
①加框處代碼有誤,請改正。
②請?jiān)趧澗€處填入合適的代碼。
(3)實(shí)現(xiàn)線路規(guī)劃的部分Python程序如下,請?jiān)趧澗€處填入合適的代碼。