学进去

最短路径问题。以m*n个边长为1的正方形组成的矩形，各顶点按行优先从0开始编号，如图a所示为3*2的矩形及顶点编号。从顶点x（起点）经由各正方形的边移动到顶点y（终点）有多种移动路径，编程求解所有的最短路径。
             

图a                                                图b

（1）分析问题，将矩形转换为计算机可处理的数据。可采用列表存储矩形中各顶点的相邻关系，如图b所示。
编写函数init，根据横向和纵向的正方形数量，返回所有顶点及其所有的相邻顶点数据。完善程序，在划线处填入合适的代码。
def init（m，n）：

tot=（m+1）*（n+1）             #顶点总数

1st=[[ ] for i in range（tot）]

for i in range（tot）：

if i > m：

1st[i].append（i-m-1）

if i<（m+1）*n：

1st[i] .append（i+m+1）

if i%（m+1）!=0：

1st[i].append（i-1）

if i%（m+1）!=m：

____

return lst
（2）分析问题，查找所有从起点到终点的最短路径。例如：査找从起点1到终点10的所有最短路径，可先查找终点10的所有相邻顶点（6，9，11），然后再逐个查找顶点6、9、11的相邻顶点，直到查找到起点1，获得所有最短路径，如图c所示，共有3条长度为3的最短路径，分别为1→2→6→10，1→5→6→10，1→5→9→10。若从起点4到终点11，共有____条最短路径。

     图c

（3）分析问题，存储查询到的路径。可采用链表结构保存路径数据，例如：查找从起点1到终点10的所有最短路径，首先将终点10的数据[10，0，-1]保存在path[0]中，然后将其相邻顶点6、9、11的数据保存到path中，path[i] [0]保存顶点的编号，path[i] [1]保存当前顶点到终点的距离，path[i] [2]保存下一顶点在path中的位置，其值为-1表示当前顶点为终点。
编写函数print_path，输出所有的最短路径。完善程序，在划线处填入合适的代码。
def print_path（x，path，length）：#x为起点编号，length为Path中有效元素个数。
cnt=0
for i in range（length）：

if path[i] [0] =x：

cnt+= 1

s="最短路径"+str（cnt）+":"

v=path[i]

while____

s=s+str（v[0]）+"，"

v=path[v[2]]

s=s+str（v[0]）+"。"

print（s）

（4）实现上述功能的Python程序如下，运行结果如图d所示。请在划线处填入合适的代码。

请输入起点：0 请输入终点：10 最短路径1：0，1，2，6，10。 最短路径2：0，1，5，6，10。 最短路径3：0，4，5，6，10。 最短路径4：0，1，5，9，10。 最短路径5：0，4，5，9，10。 最短路径6：0，4，8，9，10。

     图d

m=3                           #横向正方形数量
n=2                           #纵向正方形数量mtx=in it（m， n）
x=int（input（"请输入起点："））
y=int（input（"请输入终点："））
path=[[] for i in range（999）]
passed=[False] *len（mtx）             #保存顶点是否已途经
____
dis= 0
head = 0
tail= 0
path[tail] =[y， 0， -1]
tail+= 1
passed[y] =True
while not found：

dis+= 1

pass_dis=[False] *len（mtx）

tmp=tail

for i in range（head，tail）：

v=path[i]

for d in mtx[v[0] ] ：

if not passed[d] ：

path[tail] =____

tail+= 1

pass_dis[d] =True

if d==x：

found=True

head=tmp

for i in range（len（mtx））：             #标记已途经的顶点

if____

passed[i] =True

#输出结果
print_path（x，path，tail）