Python实现Dijkstra算法
2023-09-14 09:06:36 时间
# Dijkstra.狄杰斯特拉
import heapq
import math
def init_distance(graph, s):
distance = {s: 0}
for vertex in graph:
if vertex != s:
distance[vertex] = math.inf
return distance
def dijkstra(graph, s):
pqueue = []
heapq.heappush(pqueue, (0, s))
seen = set()
parent = {s: None}
distance = init_distance(graph, s)
while len(pqueue) > 0:
pair = heapq.heappop(pqueue)
dist = pair[0]
vertex = pair[1]
seen.add(s)
nodes = graph[vertex].keys()
for w in nodes:
if w not in seen:
if dist + graph[vertex][w] < distance[w]:
heapq.heappush(pqueue, (dist + graph[vertex][w], w))
parent[w] = vertex
distance[w] = dist + graph[vertex][w]
return parent, distance
if __name__ == '__main__':
graph_dict = {
"A": {"B": 5, "C": 1},
"B": {"A": 5, "C": 2, "D": 1},
"C": {"A": 1, "B": 2, "D": 4, "E": 8},
"D": {"B": 1, "C": 4, "E": 3, "F": 6},
"E": {"C": 8, "D": 3},
"F": {"D": 6},
}
parent_dict, distance_dict = dijkstra(graph_dict, "A")
print(parent_dict)
print(distance_dict)
相关文章
- Python实现的选择排序算法原理与用法实例分析
- Python排序算法之选择排序定义与用法示例
- Python实现的选择排序算法原理与用法实例分析
- 教你用Python实现简单监督学习算法
- 【python cookbook】【数据结构与算法】9.在两个字典中寻找相同点
- 【python cookbook】【数据结构与算法】5.实现优先级队列
- python code practice(二):KMP算法、二分搜索的实现、哈希表
- 深度学习 GPU环境 Ubuntu 16.04 + Nvidia GTX 1080 + Python 3.6 + CUDA 9.
- 【阶段三】Python机器学习13篇:机器学习项目实战:支持向量机分类的算法原理
- Python实现GWO智能灰狼优化算法优化循环神经网络分类模型(LSTM分类算法)项目实战
- Python实现贝叶斯优化器(Bayes_opt)优化循环神经网络回归模型(LSTM回归算法)项目实战
- Python实现随机分布式延迟PSO优化算法(RODDPSO)优化KMeans聚类模型项目实战
- Python实现弹性网络回归模型(ElasticNet算法)并应用网格搜索算法寻找最优参数值项目实战
- Python实现KNN(K近邻)回归模型(KNeighborsRegressor算法)并应用网格搜索算法寻找最优参数值项目实战
- Python实现SMA黏菌优化算法优化支持向量机回归模型(SVR算法)项目实战
- Python实现贝叶斯岭回归模型(BayesianRidge算法)并使用K折交叉验证进行模型评估项目实战
- 【项目实战】Python实现Naive Bayes贝叶斯分类模型(GaussianNB、MultinomialNB算法)项目实战
- 【项目实战】Python基于局部离群因子LOF算法(LocalOutlierFactor)实现信用卡数据异常值检测项目实战
- 【项目实战】Python实现LightGBM分类模型(LGBMClassifier算法)项目实战
- 贪心优先搜索算法与A*算法python实现
- 【Python算法】简单深搜练习
- 【基础知识】2、使用 python 实现排序算法
- 基于改进的离散PSO算法的FJSP的研究(Python代码实现)
- 使用OpenCV-Python+Flask+json完美实现网页与本地互相协同数据流传输: NLP模型聊天文本request传输+图像算法结果传输的解决方案