概述
假设有张8*8的地图,每个位置点id按照0-63排序。 - | 表示双向连通,箭头方向表示单向连通方向。
00 - 01 - 02 - 03 - 04 - 05 - 06 - 07
| | | | | | | |
08 - 09 - 10 - 11 - 12 - 13 - 14 - 15
| | | | | | | |
16 - 17 - 18 - 19 - 20 - 21 - 22 - 23
| | | | ↑ | | |
24 - 25 - 26 - 27 - 28 ← 29 - 30 - 31
| | ↓ ↑ | | |
32 - 33 34 ← 35 → 36 37 - 38 - 39
| | | ↓ ↑ | | |
40 - 41 → 42 → 43 → 44 - 45 - 46 - 47
| | | | | |
48 - 49 - 50 - 51 - 52 - 53 - 54 - 55
| | | | | | | |
56 - 57 - 58 - 59 - 60 - 61 - 62 - 63
外部道路均是双向连通的, 有内部道路边集合
[20,28], [28,20], [28,29], [29,28], [27,28], [28,27], [28,36], [36,28], [36,37], [37,36], [36,44], [44,36],
[44,45], [45,44],[44,52],[52,44],[35,36],[36,35],[43,44],[44,43],[27,35],[35,27],[35,43],[43,35],[43,51],[51,43],
[34,35],[35,34],[42,43],[43,42],[26,34],[34,26],[34,42],[42,34],[42,50],[50,42],[33,34],[34,33],[41,42],[42,41]
用随机数 (0,1) 决定其连通方向。
import random
def draws(orig):
graph = [ [] for i in range(0,64) ]
a = [ [' ' for i in range(0,15)] for i in range(0,15) ]
for i in range(0,15,2):
for j in range(1,15,2):
x = int(i/2) # 0
y = int((j - 1)/2) # 0
number = y * 8 + x
if orig[number][number + 8] == 1 and orig[number + 8][number] == 1 :
a[j][i] = '|tt'
graph[number].append(number + 8)
graph[number + 8].append(number)
if orig[number][number + 8] == 1 and orig[number + 8][number] > 999 :
a[j][i] = '↓tt'
graph[number + 8].append(number)
if orig[number][number + 8] > 999 and orig[number + 8][number] == 1 :
a[j][i] = '↑tt'
graph[number].append(number + 8)
if orig[number][number + 8] > 999 and orig[number + 8][number] > 999 :
a[j][i] = ' tt'
a[j-1][i] = "%02d"%(number)
for i in range(1,15,2):
for j in range(0,15,2):
x = int((i-1)/2)
y = int(j/2)
number = y * 8 + x
if orig[number][number + 1] == 1 and orig[number + 1][number] == 1 :
a[j][i] = 't-t'
graph[number].append(number + 1)
graph[number + 1].append(number)
if orig[number][number + 1] == 1 and orig[number + 1][number] > 999 :
a[j][i] = 't→t'
graph[number + 1].append(number)
if orig[number][number + 1] > 999 and orig[number + 1][number] == 1 :
a[j][i] = 't←t'
graph[number].append(number + 1)
if orig[number][number + 1] > 999 and orig[number + 1][number] > 999 :
a[j][i] = 't t'
a[j][i - 1] = "%02d"%(number)
for line in a:
print("".join(line))
return [ list(set(x)) for x in graph ]
def show():
cand = []
for i in range(0,64):
cand.append(i)
if len(cand) == 8:
print(cand)
cand = []
# generate road_matrix
def generate_map(b_ids, b_vals):
roads_matrix = [ [ float('inf') ] * 64 for i in range(0,64) ]
for i in range(0,64):
if i%8 > 0:
roads_matrix[i][i - 1] = 1
if i%8 < 7:
roads_matrix[i][i + 1] = 1
if i/8 >= 1:
roads_matrix[i][i - 8] = 1
if i/8 < 7:
roads_matrix[i][i + 8] = 1
for i, id_pair in enumerate(b_ids):
roads_matrix[id_pair[0]][id_pair[1]] = b_vals[i] if b_vals[i] == 1 else float('inf')
input_data = []
input_data.append([ float('inf') ] * 65)
for i in range(0, 64):
cand = [float('inf')]
for j in range(0, 64):
cand.append(roads_matrix[i][j])
input_data.append(cand)
return input_data, roads_matrix
通过调用下面程序获得输出结果及图的邻接矩阵
b_ids = [ [20,28], [28,20], [28,29], [29,28], [27,28], [28,27], [28,36], [36,28], [36,37], [37,36], [36,44], [44,36],
[44,45], [45,44],[44,52],[52,44],[35,36],[36,35],[43,44],[44,43],[27,35],[35,27],[35,43],[43,35],[43,51],[51,43],
[34,35],[35,34],[42,43],[43,42],[26,34],[34,26],[34,42],[42,34],[42,50],[50,42],[33,34],[34,33],[41,42],[42,41] ]
b_vals = [ random.randint(0,1) for i in range(0,len(b_ids)) ]
input_data, orig = generate_map(b_ids, b_vals)
#show()
g = draws(orig)
通过下面K最短路算法,在该图上进行k最短路寻路
import heapq
import sys
class Graph:
def __init__(self):
self.vertices = {}
def add_vertex(self, name, edges):
self.vertices[name] = edges
def get_shortest_path(self, startpoint, endpoint):
# distances使用字典的方式保存每一个顶点到startpoint点的距离
distances = {}
# 从startpoint到某点的最优路径的前一个结点
# eg:startpoint->B->D->E,则previous[E]=D,previous[D]=B,等等
previous = {}
# 用来保存图中所有顶点的到startpoint点的距离的优先队列
# 这个距离不一定是最短距离
nodes = []
shortest_path = None
lenPath = float('inf')
# Dikstra算法 数据初始化
for vertex in self.vertices:
if vertex == startpoint:
# 将startpoint点的距离初始化为0
distances[vertex] = 0
heapq.heappush(nodes, [0, vertex])
elif vertex in self.vertices[startpoint]:
# 把与startpoint点相连的结点距离startpoint点的距离初始化为对应的弧长/路权
distances[vertex] = self.vertices[startpoint][vertex]
heapq.heappush(nodes, [self.vertices[startpoint][vertex], vertex])
previous[vertex] = startpoint
else:
# 把与startpoint点不直接连接的结点距离startpoint的距离初始化为sys.maxsize
distances[vertex] = sys.maxsize
heapq.heappush(nodes, [sys.maxsize, vertex])
previous[vertex] = None
while nodes:
# 取出队列中最小距离的结点
smallest = heapq.heappop(nodes)[1]
if smallest == endpoint:
shortest_path = []
lenPath = distances[smallest]
temp = smallest
while temp != startpoint:
shortest_path.append(temp)
temp = previous[temp]
# 将startpoint点也加入到shortest_path中
shortest_path.append(temp)
if distances[smallest] == sys.maxsize:
# 所有点不可达
break
# 遍历与smallest相连的结点,更新其与结点的距离、前继节点
for neighbor in self.vertices[smallest]:
dis = distances[smallest] + self.vertices[smallest][neighbor]
if dis < distances[neighbor]:
distances[neighbor] = dis
# 更新与smallest相连的结点的前继节点
previous[neighbor] = smallest
for node in nodes:
if node[1] == neighbor:
# 更新与smallest相连的结点到startpoint的距离
node[0] = dis
break
heapq.heapify(nodes)
return distances, shortest_path, lenPath
def getMinDistancesIncrement(self, inputList):
inputList.sort()
lenList = [v[0] for v in inputList]
minValue = min(lenList)
minValue_index = lenList.index(minValue)
minPath = [v[1] for v in inputList][minValue_index]
return minValue, minPath, minValue_index
def deleteCirclesWithEndpoint(self,inputList, endpoint):
'''
该函数主要是删除类似于这样的例子: endpoint->...->endpoint-->...
'''
pathsList = [v[1] for v in inputList]
for index, path in enumerate(pathsList):
if len(path) > 1 and path[-1] == endpoint:
inputList.pop(index)
return inputList
def k_shortest_paths(self,start, finish, k = 3):
'''
:param start: 起始点
:param finish: 终点
:param k: 给出需要求的最短路数
:return: 返回K最短路和最短路长度
该算法重复计算了最短路,调用get_shortest_path()方法只是用到了起始点到其他所有点的最短距离和最短路长度
'''
distances, _, shortestPathLen = self.get_shortest_path(start, finish)
num_shortest_path = 0
paths = dict()
distancesIncrementList = [[0, finish]]
while num_shortest_path < k:
path = []
#distancesIncrementList = self.deleteCirclesWithEndpoint(distancesIncrementList,finish)
minValue, minPath, minIndex = self.getMinDistancesIncrement(distancesIncrementList)
smallest_vertex = minPath[-1]
distancesIncrementList.pop(minIndex)
if smallest_vertex == start:
path.append(minPath[::-1])
num_shortest_path += 1
paths[path[0]] = minValue + shortestPathLen
continue
for neighbor in self.vertices[smallest_vertex]:
incrementValue = minPath
increment = 0
if neighbor == finish:
continue
if distances[smallest_vertex] == (distances[neighbor] + self.vertices[smallest_vertex][neighbor]):
increment = minValue
elif distances[smallest_vertex] < (distances[neighbor] + self.vertices[smallest_vertex][neighbor]):
increment = minValue + distances[neighbor] + self.vertices[smallest_vertex][neighbor] - distances[smallest_vertex]
elif distances[neighbor] == (distances[smallest_vertex] + self.vertices[smallest_vertex][neighbor]):
increment = minValue + 2 * self.vertices[smallest_vertex][neighbor]
distancesIncrementList.append([increment, incrementValue + neighbor])
results = {}
for path in paths:
result = []
for ch in path:
result.append("%d|"%(ord(ch)-65))
results["".join(result)] = paths[path]
return results
def generate_graph(adj):
gk = Graph()
for i, line in enumerate(adj):
tmp = { chr(65+k): 1 for k in line }
gk.add_vertex(chr(65+i), tmp)
return gk
def search_k(gk, start, end, k):
start = chr(65+int(start))
end = chr(65+int(end))
distances, shortestPath, shortestPathLen = gk.get_shortest_path(start, end)
paths = gk.k_shortest_paths(start, end, k)
result = []
for path in paths:
val = path.split("|")
vals = []
for v in val:
if len(v) > 0: vals.append(int(v))
result.append((vals, paths[path]))
return result
gk = generate_graph(g)
result = search_k(gk, 1, 44, 50)
index = 1
for line in result:
print('{}:{} 最短路长度:{}'.format(index, line[0], line[1]))
index += 1
获得结果为:
1:[1, 2, 3, 4, 5, 13, 21, 29, 37, 45, 44] 最短路长度:10
2:[1, 2, 3, 4, 12, 13, 21, 29, 37, 45, 44] 最短路长度:10
3:[1, 2, 3, 11, 12, 13, 21, 29, 37, 45, 44] 最短路长度:10
4:[1, 2, 10, 11, 12, 13, 21, 29, 37, 45, 44] 最短路长度:10
5:[1, 9, 10, 11, 12, 13, 21, 29, 37, 45, 44] 最短路长度:10
6:[1, 2, 3, 4, 12, 20, 21, 29, 37, 45, 44] 最短路长度:10
7:[1, 2, 3, 11, 12, 20, 21, 29, 37, 45, 44] 最短路长度:10
8:[1, 2, 10, 11, 12, 20, 21, 29, 37, 45, 44] 最短路长度:10
9:[1, 9, 10, 11, 12, 20, 21, 29, 37, 45, 44] 最短路长度:10
10:[1, 2, 3, 11, 19, 20, 21, 29, 37, 45, 44] 最短路长度:10
11:[1, 2, 10, 11, 19, 20, 21, 29, 37, 45, 44] 最短路长度:10
12:[1, 9, 10, 11, 19, 20, 21, 29, 37, 45, 44] 最短路长度:10
13:[1, 2, 10, 18, 19, 20, 21, 29, 37, 45, 44] 最短路长度:10
14:[1, 9, 10, 18, 19, 20, 21, 29, 37, 45, 44] 最短路长度:10
15:[1, 9, 17, 18, 19, 20, 21, 29, 37, 45, 44] 最短路长度:10
最后
以上就是超帅小熊猫为你收集整理的通过python实现K短路算法,并绘制地图。的全部内容,希望文章能够帮你解决通过python实现K短路算法,并绘制地图。所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复