(python)이코테-미래도시

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘이다.

노드의 갯수가 n일때 시간 복잡도는 O(n^3)이다.

점화식 D(ab)=min(D(ab),D(ak)+D(kb))

3중 반복문을 이용해서 위 점화식에따라 최단거리 테이블을 갱신해준다.
'a에서 b로 가는 최소비용'과 'a에서 k를 거쳐 b로 가는 비용'을 비교하여 더 작은 값으로 갱신하겠단 뜻 !

미래도시 문제는 전형적인 플로이드 워셜 알고리즘 문제이올시다.

#플로이드 워셜 알고리즘 
#무한을 의미
INF =int(1e9)

#노드 개수, 간선 개수 입력받기
n,m=map(int,input().split())
#2차원 리스트 만들고, 모든 값 무한으로 초기화
graph=[[INF]*(n+1) for _ in range(n+1)]

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

#각 간선 정보 받아 그값으로 초기화 , 가중치는 모두 1
for _ in range(m):
    a,b=map(int,input().split())
    graph[a][b]=1
    graph[b][a]=1

#거쳐 갈 노드 x와 최종 목적지 노드 k를 입력받기
x,k=map(int,input().split())

#점화식에 따라 플로이드 워셜 알고리즘 수행
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])

#수행된 결과 출력
distance=graph[1][k]+graph[k][x]

#도달할 수 없는 경우, -1 출력
if distance >= INF:
    print("-1")
#도달할 수 있다면 최단 거리 출력
else:
    print(distance)