Python使用Dijkstra算法实现求解图中最短路径距离问题详解
26 浏览量
2020-09-20
12:08:27
上传
评论 4
收藏 112KB PDF 举报
Python使用使用Dijkstra算法实现求解图中最短路径距离问题详解算法实现求解图中最短路径距离问题详解
主要介绍了Python使用Dijkstra算法实现求解图中最短路径距离问题,简单描述了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):
剩余18页未读，继续阅读
资源评论
