16-3강. 최단경로 알고리즘 (Shortest Path Algorithm) (3)

이전 강좌 첨부,,

 

 

 

16-3강. 최단경로 알고리즘 (Shortest Path Algorithm) (3)

 

이전 강좌,,, Bellman-Ford Algo- 나 Dijkstra Algo-는 one-to-all 알고리즘이었다.

이번 강좌에서는 all-to-all 알고리즘에 대해 공부한다.

 

all-to-all 알고리즘의 하나가 Floyd Algorithm 혹은 Floyd-Warshall Algorithm이다.

 

Floyd-Warshall 알고리즘

- 가중치 방향 그래프 G=(V, E), V={1, 2, ..., n} (노드들에는 1번부터 n번까지 번호가 붙어 있다..)

- 모든 노드 쌍들 간의 최단경로의 길이를 구함

- d의 k승[i, j]

   ㄴ 중간에 노드집합 {1, 2, ..., k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단경로의 길이

 

 

 

 

 

 

www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/lecture/4115?tab=curriculum

영리한 프로그래밍을 위한 알고리즘 강좌 - 인프런