如何用Python寫貝爾曼-福德演算法?
Sep 22, 2023 am 08:01 AM
Python直式程式設計
演算法實現
貝爾曼-福德演算法
如何用Python寫貝爾曼-福特演算法?
貝爾曼-福特演算法(Bellman-Ford Algorithm)是一種解決帶有負權邊的單源最短路徑問題的演算法。本文將介紹如何使用Python編寫貝爾曼-福特演算法,並提供具體程式碼範例。
貝爾曼-福特演算法的核心思想是透過逐步迭代來優化路徑,直到找到最短路徑為止。演算法的步驟如下:
- 建立一個陣列dist[],儲存從源點到其他頂點的最短距離。
- 將dist[]陣列的所有元素初始化為無窮大,但來源點的距離為0。
- 經過n-1次迭代,對於每條邊(u, v):
1) 如果dist[v] > dist[u] weight(u, v),則更新dist[ v]為dist[u] weight(u, v)。 - 檢查是否有負權環。對於每條邊(u, v):
1) 如果dist[v] > dist[u] weight(u, v),則存在負權環,無法確定最短路徑。 - 如果不存在負權環,則最短路徑已經被計算出來,dist[]陣列即為最短路徑。
以下是用Python編寫的貝爾曼-福特演算法的程式碼範例:
class Graph: def __init__(self, vertices): self.V = vertices self.graph = [] def add_edge(self, u, v, w): self.graph.append([u, v, w]) def bellman_ford(self, src): dist = [float("Inf")] * self.V dist[src] = 0 for _ in range(self.V - 1): for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: dist[v] = dist[u] + w for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: print("图中存在负权环,无法确定最短路径") return self.print_solution(dist) def print_solution(self, dist): print("顶点 最短距离") for i in range(self.V): print(i, " ", dist[i]) # 示例用法 g = Graph(5) g.add_edge(0, 1, -1) g.add_edge(0, 2, 4) g.add_edge(1, 2, 3) g.add_edge(1, 3, 2) g.add_edge(1, 4, 2) g.add_edge(3, 2, 5) g.add_edge(3, 1, 1) g.add_edge(4, 3, -3) g.bellman_ford(0)
登入後複製
以上範例中,創建了一個圖g,並添加了一些邊。接著呼叫bellman_ford方法來計算最短路徑並列印結果。在這個範例中,源點是0,最短路徑將被計算出來。
貝爾曼-福特演算法的時間複雜度為O(V*E),其中V為頂點數,E為邊數。在實際應用中,如果圖中存在負權環,演算法將不會停止,而會進入無限循環。因此,在使用貝爾曼-福特演算法時,應先檢查是否有負權環。
以上是如何用Python寫貝爾曼-福德演算法?的詳細內容。更多資訊請關注PHP中文網其他相關文章!
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱門文章
擊敗分裂小說需要多長時間?
3 週前
By DDD
倉庫:如何復興隊友
3 週前
By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前
By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
1 週前
By 尊渡假赌尊渡假赌尊渡假赌
公眾號網頁更新緩存難題:如何避免版本更新後舊緩存影響用戶體驗?
3 週前
By 王林

熱門文章
擊敗分裂小說需要多長時間?
3 週前
By DDD
倉庫:如何復興隊友
3 週前
By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前
By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
1 週前
By 尊渡假赌尊渡假赌尊渡假赌
公眾號網頁更新緩存難題:如何避免版本更新後舊緩存影響用戶體驗?
3 週前
By 王林

熱門文章標籤

記事本++7.3.1
好用且免費的程式碼編輯器

SublimeText3漢化版
中文版,非常好用

禪工作室 13.0.1
強大的PHP整合開發環境

Dreamweaver CS6
視覺化網頁開發工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)