文章目录狄克斯特拉算法实现算法节点实时计算消耗的权重存储父节点记录遍历过的节点找到最小权重的节点狄克斯特拉算法
狄克斯特拉算法
加权图——提高/降低某些边的权重
加权图:“边”上有了权重(例如:时间)
狄克斯特拉算法:找到总权重最小的路径
计算非加权图的最短路径——广度优先算法
计算加权图的最小权重——狄克斯特拉算法
**注意:**当图中存在负权重时,无法使用狄克斯特拉算法
实现算法
节点
狄克斯特拉算法
# ------------整个图的散列表(字典)--------
graph = {}
# 起点
graph[start] = {} # 起点是一个散列表(字典)
g
- 1
- 2
前往页