python实现dijkstra最短路由算法

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)

节点的遍历过程如下：

最短路径输出：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • python用装饰器自动注册Tornado路由详解

    第一个版本 在这个版本中,首先创建了 RouterConfig 对象,其构造方法创建了 tornado.web.Application() 并赋值为 self.Application ,在每个 Handler 上添加 @app.route 装饰器,对应的就是 RouterConfig 下面的 route 对象,其中 Handler 实例会被赋值到 handler 参数中,最后把 URL 和 Handler 对应关系添加到路由表中, URL 在每个 Handler 中创建的属性. #!/usr/b

  • python 3.5实现检测路由器流量并写入txt的方法实例

    python 3.5实现检测路由器流量并写入txt的方法实例

    前言 本文主要给大家介绍了关于利用python 3.5检测路由器流量并写入txt的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍. 环境交代:win10+python3.6 代码非常简单, 模拟登陆,没有 网页标签过滤,没有 多线程,也没有 文本处理,只有涉及到字符串截取 本地文本写入,有 这么低级的代码是因为这个路由器页面非常垃圾,用不到~~~,不过这样也适合初学者观看,当然了,后续会尝试添加更多功能 首先我们对自己的需求要进行分析,新手嘛,先把复杂的东西简单化,模块化

  • Python 中urls.py:URL dispatcher（路由配置文件）详解

    Python 中urls.py:URL dispatcher（路由配置文件）详解

    urls.py:URL dispatcher(路由配置文件) URL配置(URLconf)就像是Django所支撑网站的目录.它的本质是URL模式以及要为该URL模式调用的视图函数之间的映射表.以这样的方式告诉Django,对于这个URL调用这段代码,对于那个URL调用那段代码.url的加载就是从配置文件中开始. urlpatterns的两种形式 没有前缀的情况,使用的列表(推荐方式) URL模式 urlpatterns = [ url(正则表达式, view函数, 参数, 别名, 前缀), ]

  • Python实现TCP探测目标服务路由轨迹的原理与方法详解

    本文实例讲述了Python实现TCP探测目标服务路由轨迹的原理与方法.分享给大家供大家参考,具体如下: 一 点睛 在此次实践中,通过scapy的traceroute()方法实现探测机到目标服务器的路由轨迹,整个过程的原理见下图,首先通过探测机以SYN方式进行TCP服务扫描,同时启动tcpdump进行抓包,捕获扫描过程经过的所有路由点,再通过graph()方法进行路由IP轨迹绘制,中间调用ASN映射查询IP地理信息并生成svg流程文档,最后使用ImageMagick工 具将svg格式转换成png,

  • Python3控制路由器——使用requests重启极路由.py

    通过本文给大家介绍Python3控制路由器--使用requests重启极路由.py的相关知识,代码写了相应的注释,以后再写成可以方便调用的模块. 用fiddler抓包可以看到很多HTTP头,经过尝试发现不是都必须的. 'Upgrade-Insecure-Requests':1,#必要项,值为1 'Content-Type':'application/x-www-form-urlencoded',#必要项 否则取不到服务顺响应返回的Set-Cookie """ python3控

  • Python操作RabbitMQ服务器实现消息队列的路由功能

    Python使用Pika库(安装:sudo pip install pika)可以操作RabbitMQ消息队列服务器(安装:sudo apt-get install rabbitmq-server),这里我们来看一下MQ相关的路由功能. 路由键的实现 比如有一个需要给所有接收端发送消息的场景,但是如果需要自由定制,有的消息发给其中一些接收端,有些消息发送给另外一些接收端,要怎么办呢?这种情况下就要用到路由键了. 路由键的工作原理:每个接收端的消息队列在绑定交换机的时候,可以设定相应的路由键.发送

  • Python Django基础二之URL路由系统

    MVC和MTV框架 MVC Web服务器开发领域里著名的MVC模式,所谓MVC就是把Web应用分为模型(M),控制器(C)和视图(V)三层,他们之间以一种插件式的.松耦合的方式连接在一起,模型负责业务对象与数据库的映射(ORM),视图负责与用户的交互(页面),控制器接受用户的输入调用模型和视图完成用户的请求,其示意图如下所示: | M:models数据库相关:V:views视图相关 C:controller控制器 url分发 | MTV Django的MTV模式本质上和MVC是一样的,也是为了各

  • Python采用socket模拟TCP通讯的实现方法

    本文实例讲述了Python采用socket模拟TCP通讯的实现方法.分享给大家供大家参考.具体实现方法如下: 对于TCP server端的创建而言,分为如下几个步骤: 创建socket对象(socket):其中两个参数分别为Address Family(如AF_INET为IPV4,AF_INET6为IPV6,AF_UNIX为UNIX域协议族).socket类型(如SOCK_STREAM为TCP,SOCK_DGRAM为UDP). 绑定服务器地址(bind):参数为服务器地址二元组. 监听(list

  • python实现多线程暴力破解登陆路由器功能代码分享

    运行时请在其目录下添加user.txt passwd.txt两文件.否则会报错.程序没有加异常处理.代码比较挫..... 复制代码 代码如下: #coding:utf-8- import base64 import urllib2 import Queue import threading,re,sys queue = Queue.Queue() class Rout_thread(threading.Thread): def __init__(self,queue,passwd): threa

  • 用Python实现一个简单的多线程TCP服务器的教程

    用Python实现一个简单的多线程TCP服务器的教程

    最近看<python核心编程>,书中实现了一个简单的1对1的TCPserver,但是在实际使用中1对1的形势明显是不行的,所以研究了一下如何在server端通过启动不同的线程(进程)来实现每个链接一个线程. 其实python在类的设计上已经考虑到了这一方面的需求,我们只要在自己的server上继承一下SocketServer.BaseRequestHandler就可以了. server端代码如下: #!/usr/bin/env python import SocketServer from t

随机推荐