算法之最短路径

本节内容

需求提出
思路分析
源代码分析

1.需求提出

需求：之前写过一个求迷宫路径的算法解决思路，现在需求升级了，光找到路径并不能满足需求，可能该迷宫中含有多条从起点到终点的路径，怎么选择一条最优路径，使得从起点到终点的路径最短？

2.思路分析

假设迷宫模型如下：

 1 maze= [
 2     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 3     [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
 4     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
 5     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1],
 6     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
 7     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
 8     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
 9     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
10     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
11     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
12     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
13     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
14     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
15     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
16 ]

从左上角的第二行第一列进来，到右下角的倒数第二行最后一列的位置出来，1代表的是用围墙堵死的位置，0代表的是可以通过的位置。那么从入口到出口之间可以有多条路径，选择一条最短路径就成了问题。

为了解决这个问题，可以设定每个可以到达的位置的权值，因为0和1已经被占用了，所以权值从2开始，入口处位置的权值设置为2，然后每往前走一步的位置，权值增加1。这种情况下方向没有之前的8个方向了，只有[N,E,S,W]四个方向，否则权值设置将会导致混乱。。。

权值设置完以后，迷宫就变成下面这样了：

 1 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   
 2 2   3   4   5   6   7   8   9   1   33  34  35  36  37  38  39  1   
 3 1   4   5   6   7   8   9   10  1   32  1   36  37  38  39  40  1   
 4 1   5   6   7   8   9   10  11  1   31  1   37  38  39  1   41  1   
 5 1   6   7   8   9   10  11  12  1   30  1   38  39  40  41  42  1   
 6 1   7   8   9   10  11  12  13  1   29  1   39  40  41  42  43  1   
 7 1   8   9   10  11  12  13  14  1   28  1   40  41  42  43  44  1   
 8 1   9   10  11  12  13  14  15  1   27  1   41  42  43  44  45  1   
 9 1   10  11  12  13  14  15  16  1   26  1   42  43  44  45  46  1   
10 1   11  12  13  14  15  16  17  1   25  1   43  44  45  46  47  1   
11 1   12  13  14  15  16  17  18  1   24  1   44  45  46  47  48  1   
12 1   13  14  15  16  17  18  19  1   23  1   45  46  47  48  49  1   
13 1   14  15  16  17  18  19  20  21  22  1   46  47  48  49  50  51  
14 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1

把整个迷宫能够走的位置都设置好权值之后，从终点位置往回走，只要下一位置的权值比当前位置的权值低（前提是权值不能为1，是1的话就是墙，而且下一位置的权值最少只会比当前位置的权值少1）那么就把下一位置添加到path这个列表中，到最后将走到起点，这时候path列表里面就是存的一个反向的路径了，再将列表反转一下，就是一个最短路径了。

　３.源代码分析

源代码如下：

 1 #!/usr/bin/env python
 2 # encoding:utf-8
 3 # __author__: huxianglin
 4 # date: 2016-09-06
 5 # blog: http://huxianglin.cnblogs.com/ http://xianglinhu.blog.51cto.com/
 6 
 7 maze= [  # 定义迷宫
 8     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 9     [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
10     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
11     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1],
12     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
13     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
14     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
15     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
16     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
17     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
18     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
19     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
20     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
21     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
22 ]
23 MOVE = [[0, -1, "N"], [1, 0, "E"], [0, 1, "S"], [-1, 0, "W"]]  # 定义的四个方向坐标的移动
24 
25 def shortest_path(start_x,start_y,end_x,end_y):
26     global maze  # 声明maze是使用的globale作用域的变量
27     maze[start_y][start_x]=2  # 设置起始位置的权值为2
28     Queue=[]  # 设置一个空队列用来在设置权值的时候存储邻居节点
29     while True:
30         for i in range(4):  # 按照[n,e,s,w]四个方向轮询寻找邻居节点
31             new_start_x,new_start_y=start_x+MOVE[i][0],start_y+MOVE[i][1]  # 找到的邻居节点的坐标
32             if maze[new_start_y][new_start_x]==0:  # 只有当邻居节点是0的时候才对邻居节点进行赋权值的操作
33                 maze[new_start_y][new_start_x]=maze[start_y][start_x]+1  # 给邻居节点赋权值在自身权值基础上加1
34                 if new_start_x==end_x and new_start_y==end_y:  # 假如邻居节点就是出口节点，那么跳出本次循环
35                     break
36                 Queue.append([new_start_x,new_start_y])  # 将刚赋值的邻居节点压入到Queue队列中以供之后使用
37         if new_start_x==end_x and new_start_y==end_y:  # 假如邻居节点就是出口节点，跳出赋值循环
38             break
39         if not Queue:  # 假如队列中没有元素了，也退出赋值循环
40             print("没有路径")
41             break
42         start_x,start_y=Queue.pop(0)  # 取出队列中的第一个元素并对其周边的邻居节点进行赋值操作
43     #经过上面这些步骤之后，迷宫已经被设置完权值了，下面就是怎样在已赋值好权值后的迷宫中找到一条最短路径了。
44 
45     path,Count,here=[],maze[end_y][end_x]-2,[end_x,end_y]   
46     for i in range(Count-1,-1,-1):  # 因为权值是从2开始的，所以我这里把权值赋初始值的时候就在出口节点权值基础上减去2
47         path.append(here)  # 将该节点添加到path列表中
48         for j in range(4):  # 按照[n,e,s,w]四个方向轮询寻找邻居节点
49             if end_x+MOVE[j][0] in range(len(maze[0])) and end_y+MOVE[j][1] in range(len(maze)):  # 判断邻居节点是否越界
50                 new_end_x,new_end_y=end_x+MOVE[j][0],end_y+MOVE[j][1]  # 没有越界时找到邻居节点的坐标
51                 if maze[new_end_y][new_end_x]==i+2:  # 假如邻居节点的权值比当前节点坐标小1的话，就说明邻居节点在最优路径上
52                     end_x,end_y=new_end_x,new_end_y # 将该邻居节点设置成当前节点并终止之前的再寻找邻居节点过程，寻找下个邻居节点
53                     break
54         here=[end_x,end_y]  # 将该邻居节点添加到path列表中
55     path.reverse() # 经过上面的循环后，得到的path列表里面存储的节点是从终点到起点的路径，将该路径反转一下，就能得到一条最优路径
56     return path
57 
58 if __name__ == "__main__":
59     start_x, start_y = 0, 1  # 设置起始位置坐标
60     end_x, end_y = 16, 12  # 设置结束位置坐标
61     path=shortest_path(start_x,start_y,end_x,end_y)  # 调用shortest_path函数寻找最短路径
62     for i in maze:  # 打印加上权值以后的迷宫
63         for j in i:
64             print("%s	"%j,end="")
65         print()
66     print(path)  # 打印最短路径