최단 경로 알고리즘: 플로이드 워셜

모든 지점에서 다른 모든 지점까지의 최단거리를 구해야 하는 경우에 사용하는 알고리즘

 

graph[a][b]=min(graph[a][b],graph[a][k]+graph[k][b])

 

graph[a][b]는 a에서 b까지 가는 최단거리를 의미한다

 

a에서 b까지의 최단거리와, 

a에서k까지 갔다가 k에서 b 까지 가는 (k를 거쳐가는)최단거리를 비교해, 더 짧은 경로를 graph에 갱신시키는 방법이다

 

"""
시간복잡도가 O(N^3)이므로
간선의개수가 500개 이하일 때만 사용해야겠다
"""

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 i in range(m):
    a,b,c=map(int,input().split())
    graph[a][b]=c #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])

#결과출력
for i in range(1,n+1):
    for j in range(1,n+1):
        if graph[i][j]==INF:
            print("INF")
        else:
            print(graph[i][j],end=' ')
    print()

삼중반복을 한다...

시간복잡도가 O(N^3)이다.

 

간선의 개수가 500개만 넘어가더라도 수행시간이 오래걸리게 된다