플로이드 알고리즘

(2022-08-10)

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

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

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

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

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

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

그래프 알고리즘
   1. 그래프 알고리즘   2. 그래프 순회 (DFS,BFS)   3. 깊이 우선 탐색 (DFS)   4. 너비 우선 탐색 (BFS)   5. 위상 정렬   6. 최소 신장 트리   7. 최단 경로   8. 다익스트라 알고리즘   9. 플로이드 알고리즘  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"