您現在的位置是:電腦技術吧?>? 基礎知識 ??>??遍歷所有點的最短路徑python,最短路徑算法??>??正文詳情

遍歷所有點的最短路徑python,最短路徑算法

符浩瀚2019-11-28 15:02:02 人圍觀
簡介Python實現Floyd算法本文將與大家分享Python無向圖的最短路徑算法:請大家多多指教并繼續改進。(中文字符串已被修改,因此py2ex不受中文字符的影響)。你可以參考你想學的算法,很

本文給大家分享的是python 無向圖最短路徑算法:請各位大大指教,繼續改進。

(修改了中文字符串,使py2exe中文沒煩惱),需要的朋友可以參考下一心想學習算法,很少去真正靜下心來去研究,前幾天趁著周末去了解了最短路徑的資料,用python寫了一個最短路徑算法。

算法是基于帶權無向圖去尋找兩個點之間的最短路徑,數據存儲用鄰接矩陣記錄。

首先畫出一幅無向圖如下,標出各個節點之間的權值。

其中對應索引:A 0B 1C 2D3E 4F 5G 6鄰接矩陣表示無向圖:

算法思想是通過Dijkstra算法結合自身想法實現的。

大致思路是:從起始點開始,搜索周圍的路徑,記錄每個點到起始點的權值存到已標記權值節點字典A,將起始點存入已遍歷列表B,然后再遍歷已標記權值節點字典A,搜索節點周圍的路徑,如果周圍節點存在于表B,比較累加權值,新權值小于已有權值則更新權值和來源節點,否則什么都不做;如果不存在與表B,則添加節點和權值和來源節點到表A,直到搜索到終點則結束。

這時最短路徑存在于表A中,得到終點的權值和來源路徑,向上遞推到起始點,即可得到最短路徑,下面是代碼:? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 # -*-coding:utf-8 -*- class DijkstraExtendPath(): def __init__(self, node_map): self.node_map = node_map self.node_length = len(node_map) self.used_node_list = [] self.collected_node_dict = {} def __call__(self, from_node, to_node): self.from_node = from_node self.to_node = to_node self._init_dijkstra() return self._format_path() def _init_dijkstra(self): self.used_node_list.append(self.from_node) self.collected_node_dict[self.from_node] = [0, -1] for index1, node1 in enumerate(self.node_map[self.from_node]): if node1: self.collected_node_dict[index1] = [node1, self.from_node] self._foreach_dijkstra() def _foreach_dijkstra(self): if len(self.used_node_list) == self.node_length - 1: return for key, val in self.collected_node_dict.items(): # 遍歷已有權值節點 if key not in self.used_node_list and key != to_node: self.used_node_list.append(key) else: continue for index1, node1 in enumerate(self.node_map[key]): # 對節點進行遍歷 # 如果節點在權值節點中并且權值大于新權值 if node1 and index1 in self.collected_node_dict and self.collected_node_dict[index1][0] node1 val[0]: self.collected_node_dict[index1][0] = node1 val[0] # 更新權值 self.collected_node_dict[index1][1] = key elif node1 and index1 not in self.collected_node_dict: self.collected_node_dict[index1] = [node1 val[0], key] self._foreach_dijkstra() def _format_path(self): node_list = [] temp_node = self.to_node node_list.append((temp_node, self.collected_node_dict[temp_node][0])) while self.collected_node_dict[temp_node][1] != -1: temp_node = self.collected_node_dict[temp_node][1] node_list.append((temp_node, self.collected_node_dict[temp_node][0])) node_list.reverse() return node_list def set_node_map(node_map, node, node_list): for x, y, val in node_list: node_map[node.index(x)][node.index(y)] = node_map[node.index(y)][node.index(x)] = val if __name__ == __main__: node = ['A', 'B', 'C', 'D', 'E', 'F', 'G'] node_list = [('A', 'F', 9), ('A', 'B', 10), ('A', 'G', 15), ('B', 'F', 2), ('G', 'F', 3), ('G', 'E', 12), ('G', 'C', 10), ('C', 'E', 1), ('E', 'D', 7)] node_map = [[0 for val in xrange(len(node))] for val in xrange(len(node))] set_node_map(node_map, node, node_list) # A --; D from_node = node.index('A') to_node = node.index('D') dijkstrapath = DijkstraPath(node_map) path = dijkstrapath(from_node, to_node) print path 運行結果:

再來一例:? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 !-- lang: python -- # -*- coding: utf-8 -*- import itertools import re import math def combination(lst): #全排序 lists=[] liter=itertools.permutations(lst) for lts in list(liter): lt=''.join(lts) lists.append(lt) return lists def coord(lst): #坐標輸入 coordinates=dict() print u'請輸入坐標:(格式為A:7 17)' p=re.compile(rd ) for char in lst: str=raw_input(char ':') dot=p.findall(str) coordinates[char]=[dot[0],dot[1]] print coordinates return coordinates def repeat(lst): #刪除重復組合 for ilist in lst: for k in xrange(len(ilist)): st=(ilist[k:],ilist[:k]) strs=''.join(st) for jlist in lst: if(cmp(strs,jlist)==0): lst.remove(jlist) for k in xrange(len(ilist)): st=(ilist[k:],ilist[:k]) strs=''.join(st) for jlist in lst: if(cmp(strs[::-1],jlist)==0): lst.remove(jlist) lst.append(ilist) print lst return lst def count(lst,coordinates): #計算各路徑 way=dict() for str in lst: str=str str[:1] length=0 for i in range(len(str)-1): x=abs( float(coordinates[str[i]][0]) - float(coordinates[str[i 1]][0]) ) y=abs( float(coordinates[ str[i] ][1]) - float(coordinates[ str[i 1] ][1]) ) length =math.sqrt(x**2 y**2) way[str[:len(str)-1]]=length return way if __name__ ==__main__: print u'請輸入圖節點:' rlist=list(raw_input()) coordinates=coord(rlist) list_directive = combination(rlist) # print 有方向完全圖所有路徑為:,list_directive # for it in list_directive: # print it print u'有方向完全圖所有路徑總數:',len(list_directive),n #無方向完全圖 list_directive=repeat(list_directive) list_directive=repeat(list_directive) # print 無方向完全圖所有路徑為:,list_directive print u'無方向完全圖所有路徑為:' for it in list_directive: print it print u'無方向完全圖所有路徑總數:',len(list_directive) ways=count(list_directive,coordinates) print u'路徑排序如下:' for dstr in sorted(ways.iteritems(), key=lambda d:d[1], reverse = False ): print dstr raw_input() 以上就是本文給大家分享的全部內容了,希望大家能夠喜歡,能夠學習python有所幫助。

版權聲明:本文由 符浩瀚 整理編輯。

原標題:最短路徑算法python,dijkstra算法python

轉載注明出處:http://www.dn9ww09s.icu/basics/14753.html

文章評論

    共有條評論來說兩句吧...

    用戶名:

    驗證碼:

作者推薦

  • 單向好友檢測網頁版,qq單向好友刪除器2019

    單向好友檢測網頁版,qq單向好友刪除器2019 相關圖片查單向好友網頁如果有一天你給一個朋友發了一條信息,而這個對象不是你的朋友,那么你就變成了一個單向的朋友。所謂單程好友,是指有你的QQ號碼的好友列表,而沒有對方的好友列...

  • 美圖秀秀電腦去皺紋,天天p圖怎么去皺紋

    美圖秀秀電腦去皺紋,天天p圖怎么去皺紋 相關圖片美圖秀秀可以除皺嗎對于美女來說,皺紋是最讓人無法忍受的。但這不是一件可以忽略的事情。但我今天要教你的不是護膚課程,而是東亞三大魔術之一的美圖修秀,幫助用戶去除照片...

  • cgi文件如何打開,cgi文件打開

    cgi文件如何打開,cgi文件打開 相關圖片cgi文件需要解壓嗎什么是CGI文件?CGI文件是HTTP服務器與您或其他計算機上的程序進行對話的工具。它的程序必須在網絡服務器上運行。大多數CGI程序都是用來解釋和處理介子表單的擴展...

  • 踩到雷區,別踩雷區

    踩到雷區,別踩雷區 相關圖片說了是雷區卻偏要踩對于很多小伙伴來說,購買手機是一筆不小的開支,所以選擇手機要謹慎。手機廣告勢不可擋似乎每部手機都很好,但有很多文字陷阱。今天的超人編輯會給你朋友...

  • python讀取json,python讀寫json文件

    python讀取json,python讀寫json文件 相關圖片python處理json數據本文主要介紹Python讀取JSON文件并將數據插入mongodb的方法。一個例子分析了Python操作JSON和mongodb數據庫的技巧。對于那些需要幫助的python 解析json...

  • 國內怎么上youtube,在youtube上都看啥

    國內怎么上youtube,在youtube上都看啥 相關圖片手機如何上YouTubeYouTube是業內最成功、最強大、最有影響力的在線視頻服務提供商之一。它是世界上最大的視頻分享網站。根據相關數據,YouTube的系統每天處理數千萬個視頻片段如何在...

  • 遍歷所有點的最短路徑python,最短路徑算法

    遍歷所有點的最短路徑python,最短路徑算法 相關圖片Python實現Floyd算法本文將與大家分享Python無向圖的最短路徑算法:請大家多多指教并繼續改進。(中文字符串已被修改,因此py2ex不受中文字符的影響)。你可以參考你想學的算法,很...

  • word文檔怎么去水印,word文檔怎么做水印

    word文檔怎么去水印,word文檔怎么做水印 相關圖片word2008水印在哪在圖片中添加水印可以增加圖片的信息量。如果水印設計得好,會給畫面增添美感。今天,超人給你帶來的教程是如何使用word給文件和圖片添加水印,這樣原始作者就可...

  • 云課堂智慧,智慧云課堂首頁

    云課堂智慧,智慧云課堂首頁 相關圖片云課堂智慧職教刷視頻智慧云人人通是一款集學習與交流為一體的學習教育軟件。教師和家長可以通過智能云來溝通孩子的學習情況,學生則可以通過智能云來學習知識,記錄自己的成...

  • b612咔嘰怎么調,b612咔嘰怎么調最佳

    b612咔嘰怎么調,b612咔嘰怎么調最佳 相關圖片怎么把b612相機調清晰最近,雪地相機和B612相機合并了!新款B612相機受到了更多孩子的喜愛。不過,很多朋友都說不知道如何調節B612卡其布的亮度。接下來,超人軟件編輯將為您介紹...

熱評文章

  • PDF轉Word軟件,pdf轉word軟件有哪些

    PDF轉Word軟件,pdf轉word軟件有哪些 相關圖片pdf轉word工具下載Word是所有上班族都需要掌握的技能,但你知道如何改變Word的格式嗎?超人編輯認為,當word被轉換成PDF時,大多數人會選擇使用word到PDF的軟件進行轉PDF轉換軟件...

  • python安裝pil模塊,python36安裝pil模塊

    python安裝pil模塊,python36安裝pil模塊 相關圖片python pil庫安裝本文主要介紹了Python中PIL模塊實現圖像格式轉換的方法,涉及到Python中PIL模塊的使用技巧,具有一定的參考價值。需要幫助的朋友可以參考下面的例子來描python image模塊安...

  • 安卓epub轉化為mobi,mobi格式文件怎么轉換epub

    安卓epub轉化為mobi,mobi格式文件怎么轉換epub 相關圖片mobi電子書轉換器格式轉換是Office中的一種不可避免的情況。今天,超人解釋了ePub和Mobi之間的轉換。電子書發布后,小朋友們一定知道這兩種格式。當我們習慣用一種格式看書時手機上...

  • 智慧云人人,智慧智慧云人人通

    智慧云人人,智慧智慧云人人通 相關圖片智慧云人人通學生版智慧云仁通是一座溝通老師、家長和孩子的橋梁。作為一款移動教學軟件,它可以在線記錄孩子成長的各個方面。那么,智能云普遍易用嗎?編輯器為您帶來了一個...

  • python做一個計算器,python做計算器

    python做一個計算器,python做計算器 相關圖片計算器編程本文主要介紹了Python概率計算器的實現方法,并結合實例分析了在Python中實現概率計算的技巧,具有一定的參考價值。需要的朋友可以參考下面的例子來描述Pytpython四則運算...

  • 百度收藏的書架在那,百度閱讀亮度太高了

    百度收藏的書架在那,百度閱讀亮度太高了 相關圖片百度小說亮度調回跟隨系統肯定有很多小朋友喜歡用百度看書,但有時他們看到一半的人需要做其他的事情,其實只要他們能收藏書籍。那百度怎么收閱讀呢?接下來,超人軟件編輯將...

  • 文檔中下劃線怎么打,表格中怎么下劃線

    文檔中下劃線怎么打,表格中怎么下劃線 相關圖片文檔中加入下劃線本文主要介紹了下劃線在Python中的使用,這是Python編程學習的基礎知識。對于您的朋友,請參考下面的文章來討論在Python中使用下劃線(uu)字符的問題文檔中如何輸入...

  • 摩拜單車有優惠活動嗎,摩拜單車

    摩拜單車有優惠活動嗎,摩拜單車 相關圖片摩拜單車怎么收費520來了。小編希望有很多狗糧。摩比自行車也推出了摩比箱式車活動,抵達520。安卓版摩比單車用戶可以掃描密碼解鎖寶箱車,騎兩分鐘就能拿到一個現金紅包,也有...

  • python的datetime,python localtime

    python的datetime,python localtime 相關圖片python nltk本文主要介紹了Python利用datetime模塊計算各種時間間隔的方法,并結合實例分析了Python常用的時間操作技巧,具有一定的參考價值。對于需要它的人,可python隨機函數...

  • 華碩帶指紋識別的筆記本,華碩筆記本指紋

    華碩帶指紋識別的筆記本,華碩筆記本指紋 相關圖片聯想帶指紋識別筆記本電腦是生活和工作中必不可少的家用電器,但它不同于普通的家用電器,它有一些你不知道的秘密,所以普通用戶會為電腦設置密碼。但畢竟密碼有很多缺陷,現...

關注微信

变脸官网查询