您好,登錄后才能下訂單哦!
今天小編給大家分享一下python的Bellman-Ford算法怎么使用的相關知識點,內容詳細,邏輯清晰,相信大部分人都還太了解這方面的知識,所以分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后有所收獲,下面我們一起來了解一下吧。
說明
1、Bellman-Ford算法是包含負權圖的單源最短路徑算法。
算法原理是對圖進行V-1放松操作,獲得所有可能的最短路徑。
2、Bellman-Ford算法可以處理負面邊緣。它的基本操作擴展是在深度上搜索,而放松操作是在廣度上搜索。
它可以在不影響結果的情況下操作負面邊緣。
Bellman-Ford算法效率低,時間復雜度高達o(V*E),v、e分別為頂點和邊數(shù)。SPFA是Bellman-Ford的隊列優(yōu)化,通過維護隊列可以大幅度減少重復計算,時間復雜度為o(k*E)。
實例
def bellman_ford( graph, source ): distance = {} parent = {} for node in graph: distance[node] = float( 'Inf' ) parent[node] = None distance[source] = 0 for i in range( len( graph ) - 1 ): for from_node in graph: for to_node in graph[from_node]: if distance[to_node] > graph[from_node][to_node] + distance[from_node]: distance[to_node] = graph[from_node][to_node] + distance[from_node] parent[to_node] = from_node for from_node in graph: for to_node in graph[from_node]: if distance[to_node] > distance[from_node] + graph[from_node][to_node]: return None, None return distance, parent def test(): graph = { 'a': {'b': -1, 'c': 4}, 'b': {'c': 3, 'd': 2, 'e': 2}, 'c': {}, 'd': {'b': 1, 'c': 5}, 'e': {'d': -3} } distance, parent = bellman_ford( graph, 'a' ) print distance print parent if __name__ == '__main__': test()
以上就是“python的Bellman-Ford算法怎么使用”這篇文章的所有內容,感謝各位的閱讀!相信大家閱讀完這篇文章都有很大的收獲,小編每天都會為大家更新不同的知識,如果還想學習更多的知識,請關注億速云行業(yè)資訊頻道。
免責聲明:本站發(fā)布的內容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。