python实现Dijkstra静态寻路算法
算法介绍
迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
当然目前也有人将它用来处理物流方面，以获取代价最小的运送方案。
算法思路
Dijkstra算法采用的是一种贪心的策略。
1.首先，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合T。
2.其次，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
3.从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，此时完成一个顶点。
4.再次，看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
5.最后，从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点（可以到达的）。
算法图形演示
现在有图如下：
每个线的权重以及标识如图所示。
第一步：
建立dis数组和T数组。
首先从起点A 开始，将A可以直接到达的顶点的权重记录在dis数组中，无法直达的记录无穷大（当前使用FFFF表示无穷大）。
将当前选择的顶点加入数组T:
第二步：
从dis数组中选择一个不在T数组中的顶点的最小权重值的顶点，当前选择为B顶点，并将B可以直接到达的顶点的相关权重和当前dis中的权重值比较，如果当前dis权重值大，则替换：
将B加入数组T:
第三步：
依次选择顶点C：
将C加入数组T:
第四步：
依次选择顶点D：
将D加入数组T:
第五步：
依次选择顶点E：
将E加入数组T:
第六步：
依次选择顶点F：
将F加入数组T:
因为所有的顶点都已经在T数组中了，算法结束。
这样就求得了从A点到各个顶点的最优解。
可以看到A顶点无法直达F顶点。
代码表示：
(代码中使用999代表FFF)
#encoding:utf-8
import copy
"""
图的表示方式
邻接矩阵
999代表无限远
"""
tuG=[[0, 10, 20, 999, 999, 999],
[999, 0, 999, 20, 70, 999],
[999, 999, 0, 50, 30, 999],
[999, 999, 999, 0, 999, 999],
[999, 999, 999, 10, 0, 999],
[999, 999, 999, 20, 20, 0]];
tuX = 6;
# 设置原点到其他定点的各个距离
dis = copy.deepcopy(tuG[0]);
def Dijkstra(G,v0):
"""
使用 Dijkstra 算法计算指定点 v0 到图 G 中任意点的最短路径的距离
INF 为设定的无限远距离值
"""
t = [];
minv = v0;
while len(t) <= tuX:
t.append(minv);
#以当前点的中心向外扩散
for w in range(0, tuX):
if dis[minv] + G[minv][w] < dis[w]:
dis[w] = dis[minv] + G[minv][w]
tmp = 1000;
for i in range(0, tuX):
tmpFlag = False;
for j in range(0, len(t)):
if i == t[j]:
tmpFlag = True;
break;
if tmpFlag == True:
continue;
if tmp > dis[i]:
tmp = dis[i];
minv = i;
if __name__ == '__main__':
Dijkstra(tuG,0);
print dis;
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。
相关推荐
-
基于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最短路由算法
Dijkstra算法:又称迪杰斯特拉算法,迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题.迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止百度百科. 注意:Dijkstra算法不能处理包含负边的图 # dijkstra算法实现,有向图和路由的源点作为函数的输入,最短路径最为输出 def dijkstra(graph,src): # 判断图是否为空,如果为空直接退出
-
Python使用Dijkstra算法实现求解图中最短路径距离问题详解
本文实例讲述了Python使用Dijkstra算法实现求解图中最短路径距离问题.分享给大家供大家参考,具体如下: 这里继续前面一篇<Python基于Floyd算法求解最短路径距离问题>的内容,这里要做的是Dijkstra算法,与Floyd算法类似,二者的用途均为求解最短路径距离,在图中有着广泛的应用,二者的原理都是老生常谈了,毕竟本科学习数据结构的同学是不可能不学习这两个算法的,所以在这里我也不再累赘,只简单概述一下这个算法的核心思想: Dijkstra算法的输入有两个参数,一个是原始的数据矩
-
Python基于Floyd算法求解最短路径距离问题实例详解
本文实例讲述了Python基于Floyd算法求解最短路径距离问题.分享给大家供大家参考,具体如下: Floyd算法和Dijkstra算法,相信大家都不陌生,在最短路径距离的求解中应该算得上是最为基础和经典的两个算法了,今天就用一点时间来重新实现一下,因为本科的时候学习数据结构才开始接触的这个算法,当时唯一会用的就是C语言了,现在的话,C语言几乎已经离我远去了,个人感觉入手机器学习以来python更得我心,因为太通俗易懂了,带给你的体验自然也是非常不错的. 当然网上 有很多的算法讲解教程,我不会在
-
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算法的代码,供大家参考,具体内容如下 # -*- 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算法
Dijkstra算法 迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题.迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止. 迪杰斯特拉算法是求从某一个起点到其余所有结点的最短路径,是一对多的映射关系,是一种贪婪算法 示例: 算法 算法实现流程思路: 迪杰斯特拉算法每次只找离起点最近的一个结点,并将之并入已经访问过结点的集合(以防重复访问,陷入死循环),然后将刚找到的
-
python实现Dijkstra静态寻路算法
算法介绍 迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路径树.该算法常用于路由算法或者作为其他图算法的一个子模块. 当然目前也有人将它用来处理物流方面,以获取代价最小的运送方案. 算法思路 Dijkstra算法采用的是一种贪心的策略. 1.首先,声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合T. 2.其次,原点 s 的路径权重被赋为 0 (dis[s] = 0).若对于顶点 s 存在能直接到达的边(s,m
-
java实现dijkstra最短路径寻路算法
[引用]迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径. 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止. 基本思想 通过Dijkstra计算图G中的最短路径时,需要指定起点s(即从顶点s开始计算). 此外,引进两个集合S和U.S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离). 初始时,S中只有起点s:U中是除s之外的顶点,并且U中顶点的路径是
-
一文教你用python编写Dijkstra算法进行机器人路径规划
目录 前言 一.算法原理 二.程序代码 三.运行结果 四. A*算法:Djikstra算法的改进 总结 前言 为了机器人在寻路的过程中避障并且找到最短距离,我们需要使用一些算法进行路径规划(Path Planning),常用的算法有Djikstra算法.A*算法等等,在github上有一个非常好的项目叫做PythonRobotics,其中给出了源代码,参考代码,可以对Djikstra算法有更深的了解. 一.算法原理 如图所示,Dijkstra算法要解决的是一个有向权重图中最短路径的寻找问题,图中
-
python实现A*寻路算法
A* 算法简介 A* 算法需要维护两个数据结构:OPEN 集和 CLOSED 集.OPEN 集包含所有已搜索到的待检测节点.初始状态,OPEN集仅包含一个元素:开始节点.CLOSED集包含已检测的节点.初始状态,CLOSED集为空.每个节点还包含一个指向父节点的指针,以确定追踪关系. A* 算法会给每个搜索到的节点计算一个G+H 的和值F: F = G + H G:是从开始节点到当前节点的移动量.假设开始节点到相邻节点的移动量为1,该值会随着离开始点越来越远而增大. H:是从当前节点到目标节点的
-
Python面向对象之静态属性、类方法与静态方法分析
本文实例讲述了Python面向对象之静态属性.类方法与静态方法.分享给大家供大家参考,具体如下: 1. 静态属性:在函数前加@property,将函数逻辑"封装"成数据属性,外部直接调用函数名,如同调用属性一样.这个函数是可以调用对象和类的属性的. # -*- coding:utf-8 -*- class Room: def __init__(self,name,owner,width,length): self.name = name self.owner = owner self.
-
Python3 A*寻路算法实现方式
我就废话不多说了,直接上代码吧! # -*- coding: utf-8 -*- import math import random import copy import time import sys import tkinter import threading # 地图 tm = [ '############################################################', '#S............................#........
-
Python实现迪杰斯特拉算法并生成最短路径的示例代码
def Dijkstra(network,s,d):#迪杰斯特拉算法算s-d的最短路径,并返回该路径和代价 print("Start Dijstra Path--") path=[]#s-d的最短路径 n=len(network)#邻接矩阵维度,即节点个数 fmax=999 w=[[0 for i in range(n)]for j in range(n)]#邻接矩阵转化成维度矩阵,即0→max book=[0 for i in range(n)]#是否已经是最小的标记列表 dis=[
-
Python实现的数据结构与算法之双端队列详解
本文实例讲述了Python实现的数据结构与算法之双端队列.分享给大家供大家参考.具体分析如下: 一.概述 双端队列(deque,全名double-ended queue)是一种具有队列和栈性质的线性数据结构.双端队列也拥有两端:队首(front).队尾(rear),但与队列不同的是,插入操作在两端(队首和队尾)都可以进行,删除操作也一样. 二.ADT 双端队列ADT(抽象数据类型)一般提供以下接口: ① Deque() 创建双端队列 ② addFront(item) 向队首插入项 ③ addRe