某景区共有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)