Python実装--K最短パスアルゴリズム
15176 ワード
1枚の図の中でK本の最短経路(短い経路)を探すことを実現する.
コードテストの過程で学んだPythonの基礎知識:
1、Python文字列の切り取り操作:
str[0:3]#0位から2位の文字を切り取る
str[:#カット文字列のすべての文字
str[6]#7文字目から末尾まで切り取る
str[:-3]#最初から最後から3番目の文字まで切り取り
str[2]#3文字目を切り取る
str[-1]#最後から最初の文字を切り取る
str[:-1]#元の文字列の順序とは逆の文字列を作成
str[-3:-1]#最後から3番目と最後から1番目より前の文字を切り取る
str[-3:]#最後から3番目から最後まで切り取る
str[:-5:-3]#逆シーケンス切り取り
2、Python辞書の要素を取得する:
dict.get(x)存在しない値を読み込むと、Noneなどのデフォルト値が返されます.
dict[x]存在しない値を読み込むと、KeyError'x'などのエラーメッセージが実行されます.
printを使用してプログラムを詳細に表示できます.
3、Dijkstraアルゴリズムは改良することによって、K-最短経路アルゴリズムに変えることができる.(ネットでの実装参照)
4、最後に出力された文字列の3文字ごとに逆順序操作を行います.(コード改良)
5、経路文字列を分析し、重複する点を検出して回路を取り除く.(コード改良)
具体的な実装コードは(ネット上のソースコードを参照)
参考記事:
https://blog.csdn.net/sxt1001/article/details/80956564
https://blog.csdn.net/qingzhuyuxian/article/details/79882088
コードテストの過程で学んだPythonの基礎知識:
1、Python文字列の切り取り操作:
str[0:3]#0位から2位の文字を切り取る
str[:#カット文字列のすべての文字
str[6]#7文字目から末尾まで切り取る
str[:-3]#最初から最後から3番目の文字まで切り取り
str[2]#3文字目を切り取る
str[-1]#最後から最初の文字を切り取る
str[:-1]#元の文字列の順序とは逆の文字列を作成
str[-3:-1]#最後から3番目と最後から1番目より前の文字を切り取る
str[-3:]#最後から3番目から最後まで切り取る
str[:-5:-3]#逆シーケンス切り取り
2、Python辞書の要素を取得する:
dict.get(x)存在しない値を読み込むと、Noneなどのデフォルト値が返されます.
dict[x]存在しない値を読み込むと、KeyError'x'などのエラーメッセージが実行されます.
printを使用してプログラムを詳細に表示できます.
3、Dijkstraアルゴリズムは改良することによって、K-最短経路アルゴリズムに変えることができる.(ネットでの実装参照)
4、最後に出力された文字列の3文字ごとに逆順序操作を行います.(コード改良)
5、経路文字列を分析し、重複する点を検出して回路を取り除く.(コード改良)
具体的な実装コードは(ネット上のソースコードを参照)
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 = []
# 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)
#print('m:'+minPath)
smallest_vertex = minPath[-3:]
#print('v:'+smallest_vertex)
distancesIncrementList.pop(minIndex)
if smallest_vertex == start:
path.append(minPath[::-1])
num_shortest_path += 1
# type(path) -> list, key
paths[path[0]] = minValue + shortestPathLen
#print(paths)
# {path ; pathlen} ， {pathlen:path}
# key ， path ，
# paths[minValue + shortestPathLen] = path
continue
for neighbor in self.vertices[smallest_vertex]:
incrementValue = minPath
increment = 0
if neighbor == finish:
# deleteCirclesWithEndpoint()
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])
return paths
if __name__ == '__main__':
g = Graph() #
g.add_vertex('a01', {'a02': 11.5, 'a70': 1.8, 'a74': 0.9})
g.add_vertex('a02', {'a03': 3.6, 'a01': 11.5, 'a44': 6.5})
g.add_vertex('a03', {'a02': 3.6, 'a04': 4.9, 'a14': 7.3, 'a15': 6.6, 'a58': 2.3})
g.add_vertex('a04', {'a03': 4.9, 'a05': 6.3, 'a59': 1.1, 'a43': 2.1})
g.add_vertex('a05', {'a04': 6.3, 'a06': 1.9, 'a17': 0.9, 'a27': 1.3})
g.add_vertex('a06', {'a05': 1.9, 'a07': 3.1, 'a18': 1.2})
g.add_vertex('a07', {'a06': 3.1, 'a08': 0.9, 'a19': 1.7, 'a34': 4.8})
g.add_vertex('a08', {'a09': 3.3, 'a20': 1.9, 'a07': 0.9, 'a37': 5.7})
g.add_vertex('a09', {'a10': 5.1, 'a84': 0.6, 'a08': 3.3, 'a87': 2})
g.add_vertex('a10', {'a11': 5, 'a22': 0.8, 'a09': 5.1, 'a21': 3.2})
g.add_vertex('a11', {'a12': 0.7, 'a10': 5, 'a22': 4.4})
g.add_vertex('a12', {'a11': 0.7, 'a30': 6.6})
g.add_vertex('a13', {'a14': 5.8, 'a81': 4, 'a45': 6})
g.add_vertex('a14', {'a15': 0.8, 'a13': 5.8, 'a81': 8.2, 'a03': 7.3})
g.add_vertex('a15', {'a55': 5.7, 'a81': 8.7, 'a14': 0.8, 'a03': 6.6})
g.add_vertex('a16', {'a17': 2.4, 'a51': 3.9, 'a61': 1.9, 'a82': 3.1})
g.add_vertex('a17', {'a18': 2.1, 'a28': 4.9, 'a16': 2.4, 'a05': 0.9})
g.add_vertex('a18', {'a19': 2.5, 'a49': 3.9, 'a17': 2.1, 'a06': 1.2})
g.add_vertex('a19', {'a20': 1, 'a36': 2.2, 'a48': 3.4, 'a18': 2.5, 'a07': 1.7})
g.add_vertex('a20', {'a21': 4.1, 'a35': 1, 'a84': 4.2, 'a19': 1, 'a08': 1.9, 'a27': 6})
g.add_vertex('a21', {'a10': 3.2, 'a20': 4.1, 'a84': 1.4})
g.add_vertex('a22', {'a11': 4.4, 'a10': 0.8, 'a85': 4.8})
g.add_vertex('a23', {'a24': 7.2, 'a31': 0.3, 'a80': 7.8,'a79': 2.4})
g.add_vertex('a24', {'a25': 0.7, 'a32': 0.4, 'a23': 7.2})
g.add_vertex('a25', {'a26': 1.3, 'a33': 0.5, 'a24': 0.7, 'a42': 8.3})
g.add_vertex('a26', {'a27': 2.9, 'a34': 1.1, 'a83': 2.8, 'a25': 1.3})
g.add_vertex('a27', {'a05': 1.3, 'a20': 6, 'a26': 2.9, 'a82': 2.1})
g.add_vertex('a28', {'a29': 7.3, 'a17': 4.9, 'a36': 0.3})
g.add_vertex('a29', {'a30': 1, 'a28': 7.3, 'a46': 6.6, 'a41': 2.1})
g.add_vertex('a30', {'a12': 6.6, 'a29': 1})
g.add_vertex('a31', {'a32': 8.1, 'a23': 0.3})
g.add_vertex('a32', {'a33': 0.9, 'a37': 3.3, 'a24': 0.4, 'a31': 8.1})
g.add_vertex('a33', {'a34': 0.8, 'a39': 3.9, 'a25': 0.5, 'a32': 0.9})
g.add_vertex('a34', {'a07': 4.8, 'a26': 1.1, 'a33': 0.8})
g.add_vertex('a35', {'a36': 0.6, 'a46': 1, 'a20': 1})
g.add_vertex('a36', {'a40': 0.9, 'a28': 0.3, 'a19': 2.2, 'a35': 0.6})
g.add_vertex('a37', {'a08': 5.7, 'a38': 0.6, 'a32': 3.3})
g.add_vertex('a38', {'a39': 0.9, 'a37': 0.6})
g.add_vertex('a39', {'a86': 2.9, 'a88': 1, 'a38': 0.9, 'a33': 3.9})
g.add_vertex('a40', {'a46': 0.6, 'a41': 5.1, 'a36': 0.9, 'a47': 2.3})
g.add_vertex('a41', {'a29': 2.1, 'a40': 5.1, 'a68': 8})
g.add_vertex('a42', {'a82': 4.8, 'a25': 8.3, 'a43': 0.8, 'a78': 3.9})
g.add_vertex('a43', {'a04': 2.1, 'a42': 0.8, 'a44':1 })
g.add_vertex('a44', {'a43': 1, 'a59': 2.3, 'a02': 6.5, 'a79': 10.2})
g.add_vertex('a45', {'a71': 3.3, 'a13': 6, 'a70': 5.9})
g.add_vertex('a46', {'a29': 6.6, 'a35': 1, 'a40': 0.6})
g.add_vertex('a47', {'a40': 2.3, 'a68': 8.5, 'a48': 1.3})
g.add_vertex('a48', {'a47': 1.3, 'a67': 8.3, 'a19': 3.4, 'a49': 2.8})
g.add_vertex('a49', {'a48': 2.8, 'a18': 3.9, 'a50': 2.7})
g.add_vertex('a50', {'a49': 2.7, 'a53': 3.6, 'a51': 1.8})
g.add_vertex('a51', {'a50': 1.8, 'a52': 0.7, 'a16': 3.9})
g.add_vertex('a52', {'a51': 0.7, 'a53': 3.1, 'a63': 6.2})
g.add_vertex('a53', {'a54': 0.7, 'a50': 3.6, 'a52': 3.1})
g.add_vertex('a54', {'a66': 2.2, 'a53': 0.7, 'a65': 4.6})
g.add_vertex('a55', {'a56': 1.5, 'a63': 3.5, 'a15': 5.7})
g.add_vertex('a56', {'a60': 3, 'a62': 1.8, 'a55': 1.5, 'a57': 2})
g.add_vertex('a57', {'a56': 2, 'a58': 1.9})
g.add_vertex('a58', {'a59': 2.3, 'a57': 1.9, 'a71': 10.7, 'a03': 2.3})
g.add_vertex('a59', {'a04': 1.1, 'a60': 3.6, 'a58': 2.3, 'a44': 2.3})
g.add_vertex('a60', {'a61': 0.7, 'a56': 3, 'a59': 3.6})
g.add_vertex('a61', {'a16': 1.9, 'a62': 3.6, 'a60': 0.7})
g.add_vertex('a62', {'a63': 2.4, 'a56': 1.8, 'a61': 3.6})
g.add_vertex('a63', {'a64': 3.4, 'a52': 6.2, 'a55': 3.5, 'a62': 2.4, 'a73': 11.7})
g.add_vertex('a64', {'a65': 3.5, 'a69': 6.2, 'a63': 3.4})
g.add_vertex('a65', {'a54': 4.6, 'a64': 3.5})
g.add_vertex('a66', {'a67': 1.9, 'a54': 2.2, 'a69': 9})
g.add_vertex('a67', {'a68': 2.5, 'a48': 8.3, 'a66': 1.9})
g.add_vertex('a68', {'a41': 8, 'a47': 8.5, 'a67': 2.5})
g.add_vertex('a69', {'a66': 9, 'a64': 6.2, 'a73': 6.8})
g.add_vertex('a70', {'a45': 5.9, 'a01': 1.8})
g.add_vertex('a71', {'a58': 10.7, 'a45': 3.3})
g.add_vertex('a72', {'a73': 3.8, 'a81': 3.3})
g.add_vertex('a73', {'a63': 11.7, 'a69': 6.8, 'a72': 3.8})
g.add_vertex('a74', {'a75': 9.8, 'a78': 14.4, 'a01': 0.9})
g.add_vertex('a75', {'a78': 11.5, 'a76': 9.7, 'a74': 9.8})
g.add_vertex('a76', {'a77': 5.6, 'a80': 4.3, 'a75': 9.7})
g.add_vertex('a77', {'a78': 8.3, 'a79': 6.3, 'a76': 5.6})
g.add_vertex('a78', {'a42': 3.9, 'a74': 14.4, 'a75': 11.5, 'a77': 8.3})
g.add_vertex('a79', {'a23': 2.4, 'a44': 10.2, 'a77': 6.3})
g.add_vertex('a80', {'a23': 7.8, 'a76': 4.3})
g.add_vertex('a81', {'a72': 3.3, 'a14': 8.2, 'a13': 4, 'a15': 8.7})
g.add_vertex('a82', {'a27': 2.1, 'a16': 3.1, 'a42': 4.8, 'a83': 2.5})
g.add_vertex('a83', {'a82': 2.5, 'a26':2.8})
g.add_vertex('a84', {'a21': 1.4, 'a85': 5.1, 'a09': 0.6, 'a20': 4.2})
g.add_vertex('a85', {'a22': 4.8, 'a84': 5.1, 'a90': 4.1})
g.add_vertex('a86', {'a89': 2.6, 'a87': 2.6, 'a39': 2.9})
g.add_vertex('a87', {'a09': 2, 'a90': 4.8, 'a86': 2.6})
g.add_vertex('a88', {'a89': 3.3, 'a39': 1})
g.add_vertex('a89', {'a90': 3.7, 'a86': 2.6, 'a88': 3.3})
g.add_vertex('a90', {'a85': 4.1, 'a87': 4.8, 'a89': 3.7})
start = 'a01'
end = 'a90'
k = 250 # K
distances, shortestPath, shortestPathLen = g.get_shortest_path(start, end)
#print('{}->{} ：{}， ：{}'.format(start, end, shortestPath, shortestPathLen))
paths = g.k_shortest_paths(start, end, k)
#print(paths)
print('
{}-->{} {}- ：'.format(start, end, k))
index = 1
for path, length in paths.items():
# 3
i = 0
j = 2
realPath = ""
while j <= len(path):
temp1 = path[i:j+1]
#print(temp1[::-1])
realPath += temp1[::-1]
i += 3
j += 3
# 3
k1 = 0
k2 = 3
flag = 0;
while k1 <= len(realPath)-3:
temp2 = realPath[k1:k1+3] #
#print("2:"+temp2)
while k2 <= len(realPath)-3:
temp3 = realPath[k2:k2+3]
#print("3:"+temp3)
if temp2 == temp3:
flag = 1
break
k2 += 3
k1 += 3
k2 = k1 + 3
#
if flag==0:
print('{}:{} ：{}'.format(index, realPath, length))
index += 1
参考記事:
https://blog.csdn.net/sxt1001/article/details/80956564
https://blog.csdn.net/qingzhuyuxian/article/details/79882088