【Dijkstra】算法
迪克斯特拉算法非教学帖子，只作自我记录
详解
https://www.codespeedy.com/how-to-implement-dijkstras-shortest-path-algorithm-in-python/
wiki
https://en.m.wikipedia.org/wiki/Dijkstra%27s_algorithm
graph = {
'A': {'B': 1, 'C': 4, 'D': 2},
'B': {'A': 9, 'E': 5},
'C': {'A': 4, 'F': 15},
'D': {'A': 10, 'F': 7},
'E': {'B': 3, 'J': 7},
'F': {'C': 11, 'D': 14, 'K': 3, 'G': 9},
'G': {'F': 12, 'I': 4},
'H': {'J': 13},
'I': {'G': 6, 'J': 7},
'J': {'H': 2, 'I': 4},
'K': {'F': 6}
}
source = input('输入起点 ')
# 记录来路起点来路设置为起点
came_from = {source:source}
# 记录已经遍历的结点
passed_points =
# 记录起点到其它结点的最小值
queue = {}
for i in graph:
queue = float('inf')
came_from = None
# 起点设置为0
queue = 0
# 排序
queue = sorted(queue.items(), key=lambda x: x)
while queue:
# pop出边权重最小的结点
min_point = queue.pop(0)
# 格式转换，下面取出数据
queue = dict(queue)
# 遍历这个结点的邻接表
for i in graph]:
# 如果i还没遍历
if i not in passed_points:
# 计算如果走这个结点的花费
comp = min_point + graph]
# 如果这个花费更小（比原来的路）
if queue > comp:
# 更新花费
queue = comp
# 更新来路
came_from = (min_point, comp)
# 当前结点放到已经遍历的中
passed_points.append(i)
# 重新排序
queue = sorted(queue.items(), key=lambda x: x)
# print(came_from)
dest = input('输入终点 ')
final_path = []
p = dest
print('总共花费 ', came_from, ' 单位')
# 输出结果
while came_from != source:
final_path.append(came_from)
p = came_from
for i in final_path[::-1]:
print(i, end=' ')
还是Floyd简单些 爱了，爱了
好像听说过这个算法，但是太久了不知道做啥用的了 小白有点看不懂。 数据结构 oh 头疼 哈哈9年前数学建模用过这个算法，特么9年了。。。。
页:
[1]