黑松山资源网 Design By www.paidiu.com
Dijkstra算法:又称迪杰斯特拉算法,迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止百度百科。
注意:Dijkstra算法不能处理包含负边的图
# dijkstra算法实现,有向图和路由的源点作为函数的输入,最短路径最为输出 def dijkstra(graph,src): # 判断图是否为空,如果为空直接退出 if graph is None: return None nodes = [i for i in range(len(graph))] # 获取图中所有节点 visited=[] # 表示已经路由到最短路径的节点集合 if src in nodes: visited.append(src) nodes.remove(src) else: return None distance={src:0} # 记录源节点到各个节点的距离 for i in nodes: distance[i]=graph[src][i] # 初始化 # print(distance) path={src:{src:[]}} # 记录源节点到每个节点的路径 k=pre=src while nodes: mid_distance=float('inf') for v in visited: for d in nodes: new_distance = graph[src][v]+graph[v][d] if new_distance < mid_distance: mid_distance=new_distance graph[src][d]=new_distance # 进行距离更新 k=d pre=v distance[k]=mid_distance # 最短路径 path[src][k]=[i for i in path[src][pre]] path[src][k].append(k) # 更新两个节点集合 visited.append(k) nodes.remove(k) print(visited,nodes) # 输出节点的添加过程 return distance,path if __name__ == '__main__': graph_list = [ [0, 2, 1, 4, 5, 1], [1, 0, 4, 2, 3, 4], [2, 1, 0, 1, 2, 4], [3, 5, 2, 0, 3, 3], [2, 4, 3, 4, 0, 1], [3, 4, 7, 3, 1, 0]] distance,path= dijkstra(graph_list, 0) # 查找从源点0开始带其他节点的最短路径 print(distance,path)
节点的遍历过程如下:
最短路径输出:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
黑松山资源网 Design By www.paidiu.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
黑松山资源网 Design By www.paidiu.com
暂无评论...
更新日志
2024年10月07日
2024年10月07日
- 群星.1991-音乐工厂1·皇后大道东【音乐工厂】【WAV+CUE】
- 群星.1992-音乐工厂2·首都【音乐工厂】【WAV+CUE】
- 群星.1994-音乐工厂3·儿童乐园【音乐工厂】【WAV+CUE】
- 胡鸿钧.2021-ex:CHANGE【星梦娱乐】【WAV+CUE】
- 班得瑞原装进口《第一张新世纪专辑:仙境》1CD[APE/CUE分轨][292.3MB]
- 伍佰《摇滚教父 伍佰黄金精选 2CD》[WAV+CUE][990MB]
- 班得瑞原装进口《第二张新世纪专辑:寂静山林》1CD[APE/CUE分轨][327.1MB]
- Beyond.1989-真的见证(2024环球MQA-UHQCD限量版)【环球】【WAV+CUE】
- 陈怡婷.2024-予你的心谁来赔【福茂】【FLAC分轨】
- 陈冠希.2003-HITS.OR.MISSES【英皇娱乐】【WAV+CUE】
- 班得瑞原装进口《第三张新世纪专辑:春野》1CD[APE/CUE分轨][278.9MB]
- 班得瑞原装进口《第四张新世纪专辑:蓝色天际》1CD[APE/CUE分轨][284.8MB]
- 班得瑞原装进口《第五张新世纪专辑:迷雾森林+EP》1CD[APE/CUE分轨][334.2MB]
- 田震.1997-顺其自然(日版)【红星生产社】【WAV+CUE】
- 小虫.1996-想得太美【滚石】【WAV+CUE】