[알고리즘] 플로이드 와샬 알고리즘
정의 모든 정점에서 모든 정점으로의 최단 경로를 구하는 최단 경로 알고리즘이다. 거쳐가는 기준을 최단거리를 구한다는 특징이 있다. 코드 import math INF = math.inf def floyid(graph): for k in range(len(graph)): for i in range(len(graph)): for j in range(len(graph)): if graph[i][k] + graph[k][j] < graph[i][j]: graph[i][j] = graph[i][k] + graph[k][j] print(graph) _graph = [ [0, 5, INF, 8], [7, 0, 9, INF], [2, INF, 0, 4], [INF, INF, 3, 0] ] floyd(_graph)
2021. 10. 24.