컴퓨터공학 💻 도서관📚
벨만 포드 최단 경로 알고리즘 본문
이 문제는 간선이 음수가 될 수 있다는 조건을 제외하면 일반적인 다익스트라 알고리즘과 같은 조건이다
(음수 간선)
2번 노드 : 2 + 1 + (-2) = 1
6번 노드 : 2 + 1 + (-2) + 2 + 2 = 5
(음수 간선 사이클)
음수 간선의 순환이 포함되는 경우에는 최소비용을 특정한 값으로 결정할 수 없는 경우가 발생할 수 있다
밑에 예시에서는 음수 간선의 사이클이 발생한다
이때 싸이클에 포함되어 있는 모든 간선에 대한 값을 모두 더하면 음수의 값이 나온다
이 경우에는 싸이클을 반복적으로 도는 과정을 통해서 비용을 무한히 줄일 수 있다
그래서 그래프 내에 음수 간선의 순환이 포함되어 있다면, 최소비용, 즉 최단거리가 음의 무한인 노드가 발생한다
-4 + 2 + 1 = -2
-2 + (-2) + (-2) + ... = - 무한대
특정한 그래프에서 최단 거리를 찾을 때 음수 순환이 포함되어 있는지를 체크하고자 한다면
벨만 포드 최단 경로 알고리즘을 사용할 수 있다
벨만 포드 알고리즘의 시간 복잡도는 O(VE)로 (V : 정점의 개수) (E : 간선의 개수), 다익스트라 알고리즘에 비해
느리다
다익스트라 알고리즘은 3번 과정을 N-1번 반복하지만 모든 간선 E개를 다 확인하지는 않고
특정 노드에 붙어 있는 간선만 확인한다
즉, 다익스트라 알고리즘은 벨만 포드 알고리즘보다 더 적은 간선을 체크한다
벨만 포드 알고리즘이 기본적으로 다익스트라 알고리즘에 상위 호환이다라는 뜻이다
벨만 포드 알고리즘은 다익스트라 알고리즘보다 상위 호환이지만 시간복잡도는 더 크다
'✅🌲강의 복습 노트 > 이코테2021 알고리즘 훈련' 카테고리의 다른 글
최소 공통 조상 (0) | 2024.12.10 |
---|---|
바이너리 인덱스 트리 (0) | 2024.12.10 |
트리 자료구조 (0) | 2024.12.04 |
우선순위 큐와 힙 . 1 (0) | 2024.11.30 |
개발형 코딩 테스트 . 1 (0) | 2024.11.29 |