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,'N',5],[3,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节点的测试情况下结果为：

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!