Python实现Dijkstra算法

Dijkstra算法

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

迪杰斯特拉算法是求从某一个起点到其余所有结点的最短路径,是一对多的映射关系,是一种贪婪算法

示例:

算法

算法实现流程思路:
迪杰斯特拉算法每次只找离起点最近的一个结点,并将之并入已经访问过结点的集合(以防重复访问,陷入死循环),然后将刚找到的最短路径的结点作为中间结点来更新相邻结点的路径长度,这样循环找到图中一个个结点的最短路径。

"""
输入
graph 输入的图
src 原点
返回
dis 记录源点到其他点的最短距离
path 路径
"""
import json
def dijkstra(graph,src):
  if graph ==None:
    return None
  # 定点集合
  nodes = [i for i in range(len(graph))] # 获取顶点列表,用邻接矩阵存储图
  # 顶点是否被访问
  visited = []
  visited.append(src)
  # 初始化dis
  dis = {src:0}# 源点到自身的距离为0
  for i in nodes:
    dis[i] = graph[src][i]
  path={src:{src:[]}} # 记录源节点到每个节点的路径
  k=pre=src
  while nodes:
    temp_k = k
    mid_distance=float('inf') # 设置中间距离无穷大
    for v in visited:
      for d in nodes:
        if graph[src][v] != float('inf') and graph[v][d] != float('inf'):# 有边
          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
    if k!=src and temp_k==k:
      break
    dis[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(nodes)
  return dis,path
if __name__ == '__main__':
  # 输入的有向图,有边存储的就是边的权值,无边就是float('inf'),顶点到自身就是0
  graph = [
    [0, float('inf'), 10, float('inf'), 30, 100],
    [float('inf'), 0, 5, float('inf'), float('inf'), float('inf')],
    [float('inf'), float('inf'), 0, 50, float('inf'), float('inf')],
    [float('inf'), float('inf'), float('inf'), 0, float('inf'), 10],
    [float('inf'), float('inf'), float('inf'), 20, 0, 60],
    [float('inf'), float('inf'), float('inf'), float('inf'), float('inf'), 0]]
  dis,path= dijkstra(graph, 0) # 查找从源点0开始带其他节点的最短路径
  print(dis)
  print(json.dumps(path, indent=4))

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我们的支持。如果你想了解更多相关内容请查看下面相关链接

(0)

相关推荐

  • 基于Python实现迪杰斯特拉和弗洛伊德算法

    图搜索之基于Python的迪杰斯特拉算法和弗洛伊德算法,供大家参考,具体内容如下 Djstela算法 #encoding=UTF-8 MAX=9 ''' Created on 2016年9月28日 @author: sx ''' b=999 G=[[0,1,5,b,b,b,b,b,b],\ [1,0,3,7,5,b,b,b,b],\ [5,3,0,b,1,7,b,b,b],\ [b,7,b,0,2,b,3,b,b],\ [b,5,1,2,0,3,6,9,b],\ [b,b,7,b,3,0,b,5

  • Python使用Dijkstra算法实现求解图中最短路径距离问题详解

    本文实例讲述了Python使用Dijkstra算法实现求解图中最短路径距离问题.分享给大家供大家参考,具体如下: 这里继续前面一篇<Python基于Floyd算法求解最短路径距离问题>的内容,这里要做的是Dijkstra算法,与Floyd算法类似,二者的用途均为求解最短路径距离,在图中有着广泛的应用,二者的原理都是老生常谈了,毕竟本科学习数据结构的同学是不可能不学习这两个算法的,所以在这里我也不再累赘,只简单概述一下这个算法的核心思想: Dijkstra算法的输入有两个参数,一个是原始的数据矩

  • python实现Dijkstra静态寻路算法

    算法介绍 迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路径树.该算法常用于路由算法或者作为其他图算法的一个子模块. 当然目前也有人将它用来处理物流方面,以获取代价最小的运送方案. 算法思路 Dijkstra算法采用的是一种贪心的策略. 1.首先,声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合T. 2.其次,原点 s 的路径权重被赋为 0 (dis[s] = 0).若对于顶点 s 存在能直接到达的边(s,m

  • python实现dijkstra最短路由算法

    Dijkstra算法:又称迪杰斯特拉算法,迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题.迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止百度百科. 注意:Dijkstra算法不能处理包含负边的图 # dijkstra算法实现,有向图和路由的源点作为函数的输入,最短路径最为输出 def dijkstra(graph,src): # 判断图是否为空,如果为空直接退出

  • python实现Floyd算法

    下面是用Python实现Floyd算法的代码,供大家参考,具体内容如下 # -*- coding: utf-8 -*- """ Created on Thu Jul 13 14:56:37 2017 @author: linzr """ ## 表示无穷大 INF_val = 9999 class Floyd_Path(): def __init__(self, node, node_map, path_map): self.node = node

  • Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例

    本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法).分享给大家供大家参考,具体如下: # coding:utf-8 # Dijkstra算法--通过边实现松弛 # 指定一个点到其他各顶点的路径--单源最短路径 # 初始化图参数 G = {1:{1:0, 2:1, 3:12}, 2:{2:0, 3:9, 4:3}, 3:{3:0, 5:5}, 4:{3:4, 4:0, 5:13, 6:15}, 5:{5:0, 6:4}, 6:{6:0}} # 每次找到离源点最近的一个顶

  • Python基于Floyd算法求解最短路径距离问题实例详解

    本文实例讲述了Python基于Floyd算法求解最短路径距离问题.分享给大家供大家参考,具体如下: Floyd算法和Dijkstra算法,相信大家都不陌生,在最短路径距离的求解中应该算得上是最为基础和经典的两个算法了,今天就用一点时间来重新实现一下,因为本科的时候学习数据结构才开始接触的这个算法,当时唯一会用的就是C语言了,现在的话,C语言几乎已经离我远去了,个人感觉入手机器学习以来python更得我心,因为太通俗易懂了,带给你的体验自然也是非常不错的. 当然网上 有很多的算法讲解教程,我不会在

  • 一文教你用python编写Dijkstra算法进行机器人路径规划

    目录 前言 一.算法原理 二.程序代码 三.运行结果 四. A*算法:Djikstra算法的改进 总结 前言 为了机器人在寻路的过程中避障并且找到最短距离,我们需要使用一些算法进行路径规划(Path Planning),常用的算法有Djikstra算法.A*算法等等,在github上有一个非常好的项目叫做PythonRobotics,其中给出了源代码,参考代码,可以对Djikstra算法有更深的了解. 一.算法原理 如图所示,Dijkstra算法要解决的是一个有向权重图中最短路径的寻找问题,图中

  • Python实现Dijkstra算法

    Dijkstra算法 迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题.迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止. 迪杰斯特拉算法是求从某一个起点到其余所有结点的最短路径,是一对多的映射关系,是一种贪婪算法 示例: 算法 算法实现流程思路: 迪杰斯特拉算法每次只找离起点最近的一个结点,并将之并入已经访问过结点的集合(以防重复访问,陷入死循环),然后将刚找到的

  • python实现Dijkstra算法的最短路径问题

    迪杰斯特拉(Dijkstra)算法主要是针对没有负值的有向图,求解其中的单一起点到其他顶点的最短路径算法. 1 算法原理 迪杰斯特拉(Dijkstra)算法是一个按照路径长度递增的次序产生的最短路径算法.下图为带权值的有向图,作为程序中的实验数据. 其中,带权值的有向图采用邻接矩阵graph来进行存储,在计算中就是采用n*n的二维数组来进行存储,v0-v5表示数组的索引编号0-5,二维数组的值表示节点之间的权值,若两个节点不能通行,比如,v0->v1不能通行,那么graph[0,1]=+∞ (采

  • python Dijkstra算法实现最短路径问题的方法

    本文借鉴于张广河教授主编的<数据结构>,对其中的代码进行了完善. 从某源点到其余各顶点的最短路径 Dijkstra算法可用于求解图中某源点到其余各顶点的最短路径.假设G={V,{E}}是含有n个顶点的有向图,以该图中顶点v为源点,使用Dijkstra算法求顶点v到图中其余各顶点的最短路径的基本思想如下: 使用集合S记录已求得最短路径的终点,初始时S={v}. 选择一条长度最小的最短路径,该路径的终点w属于V-S,将w并入S,并将该最短路径的长度记为Dw. 对于V-S中任一顶点是s,将源点到顶点

  • python3实现Dijkstra算法最短路径的实现

    问题描述 现有一个有向赋权图.如下图所示: 问题:根据每条边的权值,求出从起点s到其他每个顶点的最短路径和最短路径的长度. 说明:不考虑权值为负的情况,否则会出现负值圈问题. s:起点 v:算法当前分析处理的顶点 w:与v邻接的顶点 d v d_v dv​:从s到v的距离 d w d_w dw​:从s到w的距离 c v , w c_{v,w} cv,w​:顶点v到顶点w的边的权值 问题分析 Dijkstra算法按阶段进行,同无权最短路径算法(先对距离为0的顶点处理,再对距离为1的顶点处理,以此类

随机推荐