Flyod Warshall

이영구·2022년 9월 15일
0

Algorithm

목록 보기
15/19
  • Floyd Warshall 알고리즘
    : 모든 쌍의 최단경로를 구하는 알고리즘
    : 다익스트라와 bellman-Ford의 경우는 시작점이 1개일 때 구하는 알고리즘
    : 다익스트라와 벨만포드를 v번 반복하면 같은 결과를 얻을 수 있다.
    : 장점은 코드가 간단하는 점
    : 코드는 dp로 구성
    : O(V3)
for k in range(n):
	for i in range(n):
    	for j in range(n):
        	if d[i][j] > d[i][k] + d[k][j]:
            	d[i][j] = d[i][k] + d[k][j]
profile
In to the code!

0개의 댓글