没有合适的资源?快使用搜索试试~ 我知道了~
首页Python使用Dijkstra算法实现求解图中最短路径距离问题详解
Python使用Dijkstra算法实现求解图中最短路径距离问题详解
35 下载量 64 浏览量
更新于2023-03-03
评论 4
收藏 110KB PDF 举报
本文实例讲述了Python使用Dijkstra算法实现求解图中最短路径距离问题。分享给大家供大家参考,具体如下: 这里继续前面一篇《Python基于Floyd算法求解最短路径距离问题》的内容,这里要做的是Dijkstra算法,与Floyd算法类似,二者的用途均为求解最短路径距离,在图中有着广泛的应用,二者的原理都是老生常谈了,毕竟本科学习数据结构的同学是不可能不学习这两个算法的,所以在这里我也不再累赘,只简单概述一下这个算法的核心思想: Dijkstra算法的输入有两个参数,一个是原始的数据矩阵,一个是起始的顶点下标,算法的思想也很简单容易理解,在开始的时候,需要设置两个集合,用于存储顶点和路
资源详情
资源评论
资源推荐
Python使用使用Dijkstra算法实现求解图中最短路径距离问题详解算法实现求解图中最短路径距离问题详解
本文实例讲述了Python使用Dijkstra算法实现求解图中最短路径距离问题。分享给大家供大家参考,具体如下:
这里继续前面一篇《Python基于Floyd算法求解最短路径距离问题》的内容,这里要做的是Dijkstra算法,与Floyd算法类似,
二者的用途均为求解最短路径距离,在图中有着广泛的应用,二者的原理都是老生常谈了,毕竟本科学习数据结构的同学是不
可能不学习这两个算法的,所以在这里我也不再累赘,只简单概述一下这个算法的核心思想:
Dijkstra算法的输入有两个参数,一个是原始的数据矩阵,一个是起始的顶点下标,算法的思想也很简单容易理解,在开始的
时候,需要设置两个集合,用于存储顶点和路径距离,假设为A、B,A中最开始只包含有起始顶点,B中包含有其他所有的顶
点,并且B中的顶点路径的距离均为A中的起始顶点到B中各个顶点的路径距离值,之后从B中找到最短的路径,将该路径的在
B的一端的顶点加入到A中,更新B中对应的路径距离,循环往复进行下去直到遍历完B中的顶点为止。
好了,又啰嗦了这么多了,下面看一下,python实现的Dijkstra算法,我现在做的只是简单的回顾一下这些算法,并没有去优
化或者深究,所以程序都是很简单很LOW,希望见谅,毕竟水平有限,但是能达到看一遍能明白什么意思:
#!usr/bin/env python
#encoding:utf-8
'''''
__Author__:沂水寒城
功能:使用Dijkstra算法求最短路径距离
'''
import random
import time
def random_matrix_genetor(vex_num=10):
'''''
随机图顶点矩阵生成器
输入:顶点个数,即矩阵维数
'''
data_matrix=[] for i in range(vex_num):
one_list=[] for j in range(vex_num):
one_list.append(random.randint(1, 100))
data_matrix.append(one_list)
return data_matrix
def dijkstra(data_matrix, start_node):
'''''
Dijkstra求解最短路径算法
输入:原始数据矩阵,起始顶点
输出;起始顶点到其他顶点的最短距离
'''
vex_num=len(data_matrix)
flag_list=['False']*vex_num
prev=[0]*vex_num
dist=['0']*vex_num
for i in range(vex_num):
flag_list[i]=False
prev[i]=0
dist[i]=data_matrix[start_node][i] # print '----------------------------------------------------'
# print flag_list
# print prev
# print dist
flag_list[start_node]=False
dist[start_node]=0
k=0
for i in range(1, vex_num):
min_value=99999
for j in range(vex_num):
if flag_list[j]==False and dist[j]!='N':
min_value=dist[j] k=j
flag_list[k]=True
for j in range(vex_num):
if data_matrix[k][j]=='N':
temp='N'
else:
temp=min_value+data_matrix[k][j] if flag_list[j]==False and temp!='N' and temp<dist[j]:
dist[j]=temp
prev[j]=k
for i in range(vex_num):
print '顶点'+str(start_node)+'到顶点'+str(i)+'最短距离是--->'+str(dist[i])
def main_test_func(vex_num=10):
'''''
主测试函数
'''
start_time=time.time()
data_matrix=random_matrix_genetor(vex_num)
dijkstra(data_matrix,0)
end_time=time.time()
return end_time-start_time
if __name__ == '__main__':
data_matrix=[[0,2,3,'N'],[2,0,'N',5],[3,'N',0,9],['N',5,9,0]] dijkstra(data_matrix, 0)
time_list=[] print '----------------------------10顶点测试-------------------------------------'
time10=main_test_func(10)
time_list.append(time10)
print '----------------------------50顶点测试-------------------------------------'
time50=main_test_func(50)
time_list.append(time50)
print '----------------------------100顶点测试-------------------------------------'
time100=main_test_func(100)
time_list.append(time100)
print '---------------------------------时间消耗对比--------------------------------'
for one_time in time_list:
print one_time
结果如下:
顶点0到顶点0最短距离是—>0
顶点0到顶点1最短距离是—>2
顶点0到顶点2最短距离是—>3
顶点0到顶点3最短距离是—>12
—————————-10顶点测试————————————-
顶点0到顶点0最短距离是—>0
顶点0到顶点1最短距离是—>71
顶点0到顶点2最短距离是—>20
顶点0到顶点3最短距离是—>21
顶点0到顶点4最短距离是—>50
顶点0到顶点5最短距离是—>10
顶点0到顶点6最短距离是—>57
顶点0到顶点7最短距离是—>13
顶点0到顶点8最短距离是—>47
顶点0到顶点9最短距离是—>21
—————————-50顶点测试————————————-
顶点0到顶点0最短距离是—>0
顶点0到顶点1最短距离是—>6
顶点0到顶点2最短距离是—>6
顶点0到顶点3最短距离是—>4
顶点0到顶点4最短距离是—>24
顶点0到顶点5最短距离是—>13
顶点0到顶点6最短距离是—>15
顶点0到顶点7最短距离是—>14
顶点0到顶点8最短距离是—>14
顶点0到顶点9最短距离是—>6
顶点0到顶点10最短距离是—>11
顶点0到顶点11最短距离是—>15
顶点0到顶点12最短距离是—>6
顶点0到顶点13最短距离是—>10
顶点0到顶点14最短距离是—>8
顶点0到顶点15最短距离是—>8
顶点0到顶点16最短距离是—>8
顶点0到顶点17最短距离是—>6
顶点0到顶点18最短距离是—>7
顶点0到顶点19最短距离是—>19
顶点0到顶点20最短距离是—>29
顶点0到顶点21最短距离是—>10
顶点0到顶点22最短距离是—>18
顶点0到顶点23最短距离是—>10
顶点0到顶点24最短距离是—>20
顶点0到顶点25最短距离是—>3
顶点0到顶点26最短距离是—>18
顶点0到顶点27最短距离是—>13
顶点0到顶点28最短距离是—>25
顶点0到顶点29最短距离是—>9
顶点0到顶点30最短距离是—>25
顶点0到顶点31最短距离是—>32
顶点0到顶点32最短距离是—>22
顶点0到顶点33最短距离是—>2
顶点0到顶点34最短距离是—>18
顶点0到顶点35最短距离是—>26
顶点0到顶点36最短距离是—>7
顶点0到顶点37最短距离是—>19
顶点0到顶点38最短距离是—>31
顶点0到顶点39最短距离是—>50
顶点0到顶点40最短距离是—>44
顶点0到顶点41最短距离是—>3
顶点0到顶点42最短距离是—>34
顶点0到顶点43最短距离是—>5
顶点0到顶点44最短距离是—>22
顶点0到顶点45最短距离是—>38
顶点0到顶点46最短距离是—>64
顶点0到顶点47最短距离是—>24
顶点0到顶点48最短距离是—>62
顶点0到顶点49最短距离是—>20
—————————-100顶点测试————————————-
顶点0到顶点0最短距离是—>0
顶点0到顶点1最短距离是—>6
顶点0到顶点2最短距离是—>10
顶点0到顶点3最短距离是—>8
顶点0到顶点4最短距离是—>12
顶点0到顶点5最短距离是—>17
顶点0到顶点6最短距离是—>10
顶点0到顶点7最短距离是—>15
顶点0到顶点8最短距离是—>14
顶点0到顶点9最短距离是—>13
顶点0到顶点10最短距离是—>3
顶点0到顶点11最短距离是—>1
顶点0到顶点12最短距离是—>12
顶点0到顶点13最短距离是—>16
顶点0到顶点14最短距离是—>17
顶点0到顶点15最短距离是—>13
顶点0到顶点16最短距离是—>13
顶点0到顶点17最短距离是—>14
顶点0到顶点18最短距离是—>9
顶点0到顶点19最短距离是—>10
顶点0到顶点20最短距离是—>17
顶点0到顶点21最短距离是—>15
顶点0到顶点22最短距离是—>14
顶点0到顶点23最短距离是—>14
顶点0到顶点24最短距离是—>16
顶点0到顶点25最短距离是—>11
顶点0到顶点26最短距离是—>9
顶点0到顶点27最短距离是—>13
顶点0到顶点28最短距离是—>8
顶点0到顶点29最短距离是—>20
顶点0到顶点30最短距离是—>12
顶点0到顶点31最短距离是—>20
顶点0到顶点32最短距离是—>14
顶点0到顶点33最短距离是—>13
顶点0到顶点34最短距离是—>14
顶点0到顶点35最短距离是—>17
顶点0到顶点36最短距离是—>18
顶点0到顶点37最短距离是—>11
顶点0到顶点38最短距离是—>7
顶点0到顶点39最短距离是—>13
顶点0到顶点40最短距离是—>17
顶点0到顶点41最短距离是—>18
顶点0到顶点42最短距离是—>11
顶点0到顶点43最短距离是—>14
顶点0到顶点44最短距离是—>14
顶点0到顶点45最短距离是—>15
顶点0到顶点46最短距离是—>19
顶点0到顶点47最短距离是—>9
顶点0到顶点48最短距离是—>14
顶点0到顶点49最短距离是—>5
顶点0到顶点50最短距离是—>14
顶点0到顶点51最短距离是—>13
顶点0到顶点52最短距离是—>17
顶点0到顶点53最短距离是—>17
顶点0到顶点54最短距离是—>16
顶点0到顶点55最短距离是—>13
顶点0到顶点56最短距离是—>9
顶点0到顶点57最短距离是—>26
顶点0到顶点58最短距离是—>19
顶点0到顶点59最短距离是—>6
顶点0到顶点60最短距离是—>14
顶点0到顶点61最短距离是—>23
顶点0到顶点62最短距离是—>8
顶点0到顶点63最短距离是—>17
顶点0到顶点64最短距离是—>26
顶点0到顶点65最短距离是—>15
顶点0到顶点66最短距离是—>9
顶点0到顶点67最短距离是—>20
顶点0到顶点68最短距离是—>17
顶点0到顶点69最短距离是—>21
顶点0到顶点70最短距离是—>19
顶点0到顶点71最短距离是—>8
顶点0到顶点72最短距离是—>30
顶点0到顶点73最短距离是—>19
顶点0到顶点74最短距离是—>7
顶点0到顶点75最短距离是—>15
顶点0到顶点76最短距离是—>14
顶点0到顶点77最短距离是—>13
顶点0到顶点78最短距离是—>42
顶点0到顶点79最短距离是—>18
顶点0到顶点80最短距离是—>19
顶点0到顶点81最短距离是—>14
顶点0到顶点82最短距离是—>41
顶点0到顶点83最短距离是—>44
顶点0到顶点84最短距离是—>29
顶点0到顶点85最短距离是—>7
顶点0到顶点86最短距离是—>27
顶点0到顶点87最短距离是—>45
顶点0到顶点88最短距离是—>24
顶点0到顶点89最短距离是—>30
顶点0到顶点90最短距离是—>39
顶点0到顶点91最短距离是—>3
顶点0到顶点92最短距离是—>42
顶点0到顶点93最短距离是—>29
顶点0到顶点94最短距离是—>59
顶点0到顶点95最短距离是—>27
顶点0到顶点96最短距离是—>18
顶点0到顶点97最短距离是—>93
顶点0到顶点98最短距离是—>82
顶点0到顶点99最短距离是—>16
至于时间的消耗如下:
———————————时间消耗对比——————————–
0.00032901763916
0.00534200668335
0.0202090740204
在1000节点的测试情况下结果为:
—————————-1000顶点测试————————————-
顶点0到顶点0最短距离是—>0
顶点0到顶点1最短距离是—>4
顶点0到顶点2最短距离是—>3
顶点0到顶点3最短距离是—>4
顶点0到顶点4最短距离是—>3
顶点0到顶点5最短距离是—>3
顶点0到顶点6最短距离是—>3
顶点0到顶点7最短距离是—>3
顶点0到顶点8最短距离是—>3
顶点0到顶点9最短距离是—>4
顶点0到顶点10最短距离是—>4
顶点0到顶点11最短距离是—>4
剩余18页未读,继续阅读
weixin_38640150
- 粉丝: 3
- 资源: 909
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- ExcelVBA中的Range和Cells用法说明.pdf
- 基于单片机的电梯控制模型设计.doc
- 主成分分析和因子分析.pptx
- 共享笔记服务系统论文.doc
- 基于数据治理体系的数据中台实践分享.pptx
- 变压器的铭牌和额定值.pptx
- 计算机网络课程设计报告--用winsock设计Ping应用程序.doc
- 高电压技术课件:第03章 液体和固体介质的电气特性.pdf
- Oracle商务智能精华介绍.pptx
- 基于单片机的输液滴速控制系统设计文档.doc
- dw考试题 5套.pdf
- 学生档案管理系统详细设计说明书.doc
- 操作系统PPT课件.pptx
- 智慧路边停车管理系统方案.pptx
- 【企业内控系列】企业内部控制之人力资源管理控制(17页).doc
- 温度传感器分类与特点.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0