[python]floyd-walshアルゴリズム
3579 ワード
floyd-walshアルゴリズム
エッジウェイトが負または正の重み付けグラフィックで最短パスを探すアルゴリズム
すべての頂点ペア間の最短パスの長さ(または重み付け和)を求めることができます.
最短距離情報を2 Dテーブルに格納
時間複雑度:
O(V^3)、Vは頂点の個数始点i,目的地j,経路kを用いてfor文を形成する
写真の例はhttps://ko.wikipedia.org/wiki/フロイドウォーシェルアルゴリズム/を参照してください
Python Code
kは文の一番外側にある必要があります.# Vertex 개수 : n 기준
# k : 경유지
for k in range(n):
# i : 출발지
for i in range(n):
# j : 목적지
for j in range(n):
# dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
if dp[i][j] > dp[i][k] + dp[k][j] :
dp[i][j] = dp[i][k] + dp[k][j]Practice
Reference
この問題について([python]floyd-walshアルゴリズム), 我々は、より多くの情報をここで見つけました https://velog.io/@mein-figur/Python플로이드-워셜-알고리즘テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol