迪傑斯特拉
floyd算法(floyd-warshallalgorithm)又稱為弗洛伊德算法
inf_val = 9999
class floyd_path():
def __init__(self, node, node_map, path_map):
self.node = node
self.node_map = node_map
self.node_length = len(node_map)
self.path_map = path_map
self._init_floyd()
def __call__(self, from_node, to_node):
self.from_node = from_node
self.to_node = to_node
return self._format_path()
def _init_floyd(self):
for k in range(self.node_length):
for i in range(self.node_length):
for j in range(self.node_length):
tmp = self.node_map[i][k] + self.node_map[k][j]
if self.node_map[i][j] > tmp:
self.node_map[i][j] = tmp
self.path_map[i][j] = self.path_map[i][k]
print('_init_floyd is end')
def _format_path(self):
node_list = []
temp_node = self.from_node
obj_node = self.to_node
print("the shortest path is: %d"%(self.node_map[temp_node][obj_node]))
node_list.append(self.node[temp_node])
while true:
node_list.append(self.node[self.path_map[temp_node][obj_node]])
temp_node = self.path_map[temp_node][obj_node]
if temp_node == obj_node:
break;
return node_list
def set_node_map(node_map, node, node_list, path_map):
for i in range(len(node)):
## 對角線為0
node_map[i][i] = 0
for x, y, val in node_list:
node_map[node.index(x)][node.index(y)] = node_map[node.index(y)][node.index(x)] = val
path_map[node.index(x)][node.index(y)] = node.index(y)
path_map[node.index(y)][node.index(x)] = node.index(x)
if __name__ == "__main__":
node = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
node_list = [('a', 'f', 9), ('a', 'b', 10), ('a', 'g', 15), ('b', 'f', 2),
('g', 'f', 3), ('g', 'e', 12), ('g', 'c', 10), ('c', 'e', 1),
('e', 'd', 7)]
## node_map[i][j] 存儲i到j的最短距離
node_map = [[inf_val for val in range(len(node))] for val in range(len(node))]
## path_map[i][j]=j 表示i到j的最短路徑是經過頂點j
path_map = [[0 for val in range(len(node))] for val in range(len(node))]
## set node_map
set_node_map(node_map, node, node_list, path_map)
## select one node to obj node, e.g. a --> d(node[0] --> node[3])
from_node = node.index('a') //起點
to_node = node.index('e') //終點
floydpath = floyd_path(node, node_map, path_map)
path = floydpath(from_node, to_node)
print(path)
-----------------------------------------------------------------------------------------