学进去

某景区共有9个景点（编号依次为0-8），景点之间的连通情况如图所示，两个景点之间的数值表示两个景点之间的距离。小明想从编号为start的景点尽快到达编号为end的景点与同学汇合，小明应如何规划行进路线，使得行走的距离最短？并输出从起点到终点经历的景点编号。

算法思想：
1将起点到起点的距离设置为0，起点到其他景点的距离设置为无穷大
2从未标记的景点中选择距离起点最近的景点A，做标记，并收录到最优路径中
3计算与景点A相连的景点B的距离：（景点B的距离是指从起点到景点B的距离）
若景点A的距离+景点A到景点B的距离〈景点B的距离，更新景点B的距离，并将景点A设置为景点B前驱景点
编写Python程序，实现上述功能，程序运行界面如图所示。

（1）若景点3到景点4之间的距离为1，则从起点0到终点4的最短距离是______
（2）定义如下dijkstra(s)函数，参数s表示起点编号。函数的功能是求解各个景点距离起点景点的最短距离。
①加框处代码有误，请改正。
②请在划线处填入合适的代码。
def   dijkstra(s):
dist [s]=0
while True:

i=-1                  #设定一个初始值

for   j   in range(n):     #从未标记的景点编号中选择一个距离起点最近的景点编号

            if not flag[j]:
                 if :______
                       i=j
       if   i==-1:#若所有节点均已经标记
            break

#将选定的节点进行标记，同时更新节点距离

______

for   j   in range(n):

if   dist[j]>dist[i]+path[i][j]:

dist [j]=dist[i]+path[i][j]

pre[j]=i

（3）实现线路规划的部分Python程序如下，请在划线处填入合适的代码。
n=9
flag=[False]*n
pre=[-1]*n            #记录前驱
Inf=float (’inf’)     #表示无穷大
dist=[Inf]*n
path=[[0, 4, Inf, Inf, Inf, Inf, Inf, 8, Inf],
[4, 0, 8, Inf, Inf, Inf, Inf, 11, Inf],
[Inf, 8, 0, 7, Inf, 4, Inf, Inf, 4],
[Inf, Inf, 7, 0,9,14, Inf, Inf, Inf],
[Inf, Inf, Inf, 9, 0,10, Inf, Inf, Inf],
[Inf, Inf, 4, 14,10,0, 2, Inf, Inf],
[Inf, Inf, Inf, Inf, Inf, 2, 0, 1,6],
[8, 11,Inf, Inf, Inf, Inf, 1, 0, 7],
[Inf, Inf, 2, Inf, Inf, Inf, 6, 7, 0]]
start=int (input ("请输入起点景点编号(0-8):"))
end=int (input ("请输入终点景点编号(0-8):"))
①______
print ("从起点到终点的最短距离是："，②______）
print ("从起点到终点经历的景点编号依次为：",end="")
cur=end
pos=str(end)
while③______:

pos=str (pre [cur])+"→"+pos

cur=pre[cur]

print (pos)