Bellman-Ford Algorithm 벨만 포드 알고리즘

(2024-10-27)

▷ Top ▷ 정보기술(IT) ▷ 프로그래밍 ▷ 자료구조 ▷ 비선형 자료구조 (그래프,트리) ▷ 그래프 ▷ 그래프 알고리즘

1. 벨만 포드 알고리즘 (Bellman-Ford Algorithm)

  ㅇ 1958년 Richard Bellman,1962년 Lester Ford가 제안한 알고리즘을 기반으로 함

  ㅇ 그래프 상의 특징
     - 음의 가중치도 허용하는 경우
     - 순환 포함 허용

  ㅇ 방식 상의 특징
     - 간선 가중치가 음수도 처리 가능
     - 결과를 이용하여 음수 가중치 순환을 찾아낼 수 있음

  ㅇ 시간복잡도 : O(nm)
     - (n : 정점수, m : 간선수) 

  ㅇ ... (작성중) ...

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

▷ Top (분류 펼침) : 1,599개 분류 6,594건 해설