[Python]flowersalアルゴリズム

# 플로이드 워셜
INF = float('inf')
n = 4
nodes = [[1, 2, 4], [1, 4, 6], [2, 1, 3],
	[2, 3, 7], [3, 1, 5], [3, 4, 4], [4, 3, 2]]
graph = [[INF] * (n+1) for _ in range(n+1)]
for u, v, w in nodes:
    graph[u][v] = w
for k in range(1, n+1):
    graph[k][k] = 0
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
for i in graph[1:]:
    print(i[1:])

floydwalshアルゴリズムでは2次元リストを通過する隣接行列方式が用いられ,多益ツリーでは1次元リストを通過する隣接リスト方式が用いられる.
1番、2番、3番、4番には4つのノードが存在します.
kが2の場合、2番ノードを通過したすべての状況を検索します.
2番ノードを除く1番、3番、4番の3つのノードのうち、2つのノードを選択する必要があります.3P2により(1, 3), (1, 4), (3, 1), (3, 4), (4, 1), (4, 3)の計6つのケースが見つかった.
結合ではなく順序を使用する理由は、2つのノード間の重みが異なるためです.

    # k = 2 가정
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i == k or j == k or i == j:
                continue
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

この部分は,2におけるfor文n^2の探索により,n-1P2の場合の数をできるだけ見つけるコードである.
ゲートを追加すると、合計16回の探索のうち、10回でcontinueが実行されます.