플로이드 알고리즘

(2022-08-10)

1. 플로이드 (Floyd) 알고리즘 

  ㅇ 모든 쌍 최단경로 문제
     - 모든 정점으로부터, 다른 모든 정점까지의 최단 경로를 구하는 문제

     - 한편, 단일 출발지 최단경로 문제의 경우, ☞ 다익스트라 알고리즘, 벨만 포드 알고리즘 참조

  ㅇ 특징
     - 최단 경로에 포함되는 모든 부분 경로 그 자체도 최단 경로 임

  ㅇ 단계
     - 우선 그래프를 표현하는 인접 행렬을 구해 놓고,
     - 두 정점 간에 가능한 모든 경로 비용들을 비교하여 최단 거리를 구하면서,
     - 이를 저장하여 두고,
     - 전체 두 정점 간에 이를 적용하며, 최소 비용 테이블을 구함

  ㅇ ... (편집중) ...



"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"