本文實(shí)例講述了Python基于Floyd算法求解最短路徑距離問題。分享給大家供大家參考，具體如下：

Floyd算法和Dijkstra算法，相信大家都不陌生，在最短路徑距離的求解中應(yīng)該算得上是最為基礎(chǔ)和經(jīng)典的兩個(gè)算法了，今天就用一點(diǎn)時(shí)間來重新實(shí)現(xiàn)一下，因?yàn)楸究频臅r(shí)候?qū)W習(xí)數(shù)據(jù)結(jié)構(gòu)才開始接觸的這個(gè)算法，當(dāng)時(shí)唯一會(huì)用的就是C語言了，現(xiàn)在的話，C語言幾乎已經(jīng)離我遠(yuǎn)去了，個(gè)人感覺入手機(jī)器學(xué)習(xí)以來python更得我心，因?yàn)樘ㄋ滓锥耍瑤Ыo你的體驗(yàn)自然也是非常不錯(cuò)的。

當(dāng)然網(wǎng)上 有很多的算法講解教程，我不會(huì)在這里累贅Floyd是什么原理，因?yàn)橄嘈糯蠹叶际煜ぃ唵蔚卣f就是：三角不等式這個(gè)核心思想，如果我要求頂點(diǎn)A到頂點(diǎn)B之間的距離的話，我可以先找一個(gè)頂點(diǎn)C，求解頂點(diǎn)A到頂點(diǎn)C加上頂點(diǎn)C到頂點(diǎn)B的距離和，如何這個(gè)距離和小于頂點(diǎn)A直接到頂點(diǎn)B的距離的話，那么這個(gè)時(shí)候就要更新一下距離矩陣中的值，將頂點(diǎn)A到頂點(diǎn)B的距離更新為：頂點(diǎn)A到頂點(diǎn)C加上頂點(diǎn)C到頂點(diǎn)B的距離和。這就是Folyd的核心思想了，那么如果要找到全局最優(yōu)的解就要在選取中間頂點(diǎn)的過程中遍歷所有的節(jié)點(diǎn)才行，這樣就是三層for循環(huán)的結(jié)構(gòu)了，得到的時(shí)間復(fù)雜度就是O(n*n*n)，n為頂點(diǎn)的規(guī)模，其實(shí)在具體實(shí)際的應(yīng)用中，這個(gè)算法的性能還是很不錯(cuò)的對(duì)于求解小規(guī)模的圖問題的時(shí)候，如果感興趣的話可以把程序拿去做實(shí)驗(yàn)試試，直接可以運(yùn)行的，不依賴第三方的其他模塊。

下面看具體的實(shí)現(xiàn)：

#!usr/bin/env python#encoding:utf-8'''''__Author__:沂水寒城功能：使用floyd算法求最短路徑距離'''import randomimport timedef random_matrix_genetor(vex_num=10): ''''' 隨機(jī)圖頂點(diǎn)矩陣生成器 輸入：頂點(diǎn)個(gè)數(shù)，即矩陣維數(shù) ''' 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 floyd(data_matrix): ''''' 輸入：原數(shù)據(jù)矩陣，即：一個(gè)二維數(shù)組 輸出：頂點(diǎn)間距離 ''' dist_matrix=[] path_matrix=[] vex_num=len(data_matrix) for h in range(vex_num):  one_list=['N']*vex_num  path_matrix.append(one_list)  dist_matrix.append(one_list) for i in range(vex_num):  for j in range(vex_num):   dist_matrix=data_matrix   path_matrix[i][j]=j for k in range(vex_num):  for i in range(vex_num):   for j in range(vex_num):    if dist_matrix[i][k]=='N' or dist_matrix[k][j]=='N':     temp='N'    else:     temp=dist_matrix[i][k]+dist_matrix[k][j]    if dist_matrix[i][j]>temp:     dist_matrix[i][j]=temp     path_matrix[i][j]=path_matrix[i][k] return dist_matrix, path_matrixdef main_test_func(vex_num=10): ''''' 主測(cè)試函數(shù) ''' data_matrix=random_matrix_genetor(vex_num) dist_matrix, path_matrix=floyd(data_matrix) for i in range(vex_num):  for j in range(vex_num):   print '頂點(diǎn)'+str(i)+'----->'+'頂點(diǎn)'+str(j)+'最小距離為:', dist_matrix[i][j]if __name__ == '__main__': data_matrix=[['N',1,'N',4],[1,'N',2,'N'],['N',2,'N',3],[4,'N',3,'N']] dist_matrix, path_matrix=floyd(data_matrix) print dist_matrix print path_matrix time_list=[] print '------------------------------節(jié)點(diǎn)數(shù)為10測(cè)試情況------------------------------------' start_time0=time.time() main_test_func(10) end_time0=time.time() t1=end_time0-start_time0 time_list.append(t1) print '節(jié)點(diǎn)數(shù)為10時(shí)耗時(shí)為：', t1 print '------------------------------節(jié)點(diǎn)數(shù)為100測(cè)試情況------------------------------------' start_time1=time.time() main_test_func(100) end_time1=time.time() t2=end_time1-start_time1 time_list.append(t2) print '節(jié)點(diǎn)數(shù)為100時(shí)耗時(shí)為：', t2 print '------------------------------節(jié)點(diǎn)數(shù)為1000測(cè)試情況------------------------------------' start_time1=time.time() main_test_func(1000) end_time1=time.time() t3=end_time1-start_time1 time_list.append(t3) print '節(jié)點(diǎn)數(shù)為100時(shí)耗時(shí)為：', t3 print '--------------------------------------時(shí)間消耗情況為：--------------------------------' for one_time in time_list:  print one_time