python付きfloyd-walshアルゴリズム

最短パスアルゴリズム

一般的な最短パスアルゴリズムには、複数のパスアルゴリズムがあります.複数の曲線アルゴリズムは、1つのノードから他のすべてのノードまでの最短距離を求めるアルゴリズムです.これに対してflowersalアルゴリズムは,すべてのノードから他のすべてのノードへの最短距離を求めるアルゴリズムである.「流水アルゴリズム」を実装するのは簡単なので、図面にすべての距離情報が必要な場合は、「流水アルゴリズム」を使用することをお勧めします.

floyd-walshアルゴリズム

floywalshアルゴリズムは、通過したノードに基づいて距離を求める.

特定のノードを通過する距離と、1本の幹線のみで別のノードに到達する距離とを比較することにより、最短距離として最小値を指定する方法.

が実施されると、アルゴリズムは動的プログラミングであり、距離を表すマトリクス値を更新し続ける.

floywalshアルゴリズムの式は以下の通りである.

Dab=min(Dab,Da1+D1b)D_{ab} =min(D_{ab}, D_{a1}+D_{1b})Dab​=min(Dab​,Da1​+D1b​)

floodアルゴリズムを実装するには、まず、1本の幹線にしか到達できないすべての距離をマトリクスに入れなければならない.

の点火式を使用して値を求めると、1番ノードを通過したときにマトリクスはリフレッシュされません.

2ノードを通過すると、マトリクスのいくつかの値が更新されます.

このように4番ノードに繰り返すと、以下に示すように最短距離情報を含むマトリクスが完了する.

flowersalアルゴリズムを以下の問題で実装することを試みる.

ケビン・ベーコンの6次法則

n, m = map(int, input().split())

matrix = [[n]*n for _ in range(n)]        # INF를 n으로 표현했습니다.
                                          # 최단 거리는 노드의 개수보다 커질수 없기 때문입니다. 
for _ in range(m):
  a,b = map(int, input().split())
  matrix[a-1][b-1] = matrix[b-1][a-1] = 1 # 연결된 노드끼리의 거리는 모두 1입니다.
  										  # 무방향 그래프이므로 대각선 대칭으로 값을 입력합니다.
 
for i in range(n):
  matrix[i][i] = 0                        # 대각선을 0으로 초기화

for k in range(n):
  for i in range(n):
    for j in range(n):
      if matrix[i][j] > matrix[i][k] + matrix[k][j]:
        matrix[i][j] = matrix[i][k] + matrix[k][j]

result = []
for i in (matrix):
  result.append(sum(i))

print(result.index(min(result))+1)