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 randomimport timedef 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_matrixdef 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_timeif __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