Floyd Warshall

[APSP] Floyd Warshall 알고리즘

• Algorithm
• 2021년 4월 12일

벨만-포드 알고리즘과 다익스트라 알고리즘과 달리 모든 최단 경로를 구하는 알고리즘이다. (물론 두 알고리즘도 모든 정점에대해 수행하면 모든 최단 경로를 구할 수 있다.) 1. 특징 음의 가중치 허용 optimal substructure 개념 이용 배열을 이용하여 구현 밀집그래프에서 모든 edge간 경로 구할때 적합 2. Pesudo Code let dist be a |V| × |V| array of minimum distances initialized to ∞ let p be a |V| × |V| array of previous node initialized to null...