[알고리즘] 플로이드 워셜

각 단계마다 특정한 노드 k를 거쳐가는 경우를 확인한다. a에서 b로 가는 경로보다 a에서 k를 거쳐 b로 가는 경로가 더 빠른지를 검사한다.

INF=int(1e9) #무한을 의미
n=int(input()) #노드의 개수
m=int(input()) #간선의 개수
graph=[[INF]*(n+1) for _ in range(n+1)] #2차원 리스트를 만들고 무한으로 초기화

for a in range(1,n+1):
  for b in range(1, n+1):
    if a==b:
      graph[a][b]=0 #자기자신으로 가는 비용

for _ in range(m): #간선 정보 입력받기
  a,b,c = map(int,input().split())
  graph[a][b]=c

for k in range(1, n+1):
  for a in range(1, n+1):
    for b in range(1, n+1):
      graph[a][b] = min(graph[a][b], graph[a][k]+ graph[k][b]) #k를 거쳐가는 값이 더 작으면 바꿈

for a in range(1, n+1):
  for b in range(1, n+1):
    #경로가 없는 경우
    if graph[a][b]==INF:
      print("infinity")
    else:
      print(graph[a][b], end=" ")
    print()

 

시간복잡도 : O(N^3)

=> 노드의 개수가 500개 미만일 때 사용.

 

 

문제 - 미래도시

INF = int(1e9)

n, m = map(int,input().split())
graph=[[INF]*(n+1) for i in range(n+1)]
for a in range(n+1):
  for b in range(n+1):
    graph[a][b] = 0

for _ in range(m):
  a, b= map(int,input().split())
  graph[a][b] =1
  graph[b][a] =1

x, k = map(int,input().split())

for k in range(1,n+1):
  for i in range(1, n+1):
    for j in range(1, n+1):
      graph[i][j] = max(graph[i][j],graph[i][k]+graph[k][j])

d = graph[1][k] + graph[k][x]
if d!=INF:
  print(d)
else:
  print(-1)