本文實例講述了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