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

图 a

图 b

1. （1） 分析问题，将矩形转换为计算机可处理的数据。可采用列表存储矩形中各顶点的相邻关系，如图 b所示。

   编写函数init，根据横向和纵向的正方形数量，返回所有顶点及其所有的相邻顶点数据。完善程序，在划线处填入合适的代码。

   def init(m,n):

       tot=(m+1)*(n+1)    #顶点总数

       lst=[[] for i in range(tot)]

       for i in range(tot):

           if i>m:

               lst[i].append(i-m- 1)

           if i<(m+1)*n:

               lst[i].append(i+m+1)

           if i%(m+1) != 0:

               lst[i].append(i- 1)

           if i%(m+1) != m:

              

       return lst

3. （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

5. （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):    #为起点编号，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)

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

   

   m=3           #横向正方形数量

   n=2              #纵向正方形数量

   mtx=init(m,n)

   x=int(input("请输入起点:"))

   y=int(input("请输入终点:"))

   path=[[] for i in range(30)]

   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)