- 최단 경로 문제는 다음과 같이 분류할 수 있다.
- 모든 간선이 양수인 경우.
- 음수 간선이 있는 경우.
1) 음수 간선 순환은 없는 경우
2) 음수 간선 순환이 있는 경우
벨만 포드 최단 경로 알고리즘은 다익스트라 알고리즘과 유사하지만,
벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있다.
- 또한 음순 간선의 순환을 감지할 수있다.
- 벨만 포드의 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느리다.
-벨만 포드 알고리즘 동작과정
1. 출발 노드 설정
2. 최단 거리 테이블을 초기화
3. 다음의 과정을 N - 1 번 반복
1) 전체 간선 E개를 하나씩 확인
2) 각 간선을 거쳐 다른 노드로 가는 비용을 계산 하여 최단 거리 테이블 갱신
- 만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행
-이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재 하는 것.
위 예시를 벨만 포드 알고리즘으로 구현 한다면
노드와 간선의 정보와 정보를 입력받을 변수 호출 하고
이때 시간초과를 하지않기 위해 import sys 로 sys 라이브러리를 호출.
(동작과정 2번 포함)
먼저 시작 노드의 거리 값을 0으로 설정한다. (동작과정 1번)
for i in range(n) (동작과정 3번)
for j in range(m) (동작 과정 3-1 번)
최단거리 설정을 위한 cur, next_node, cost 변수 초기화
if dist~~ (동작과정 3-2번)
벨만 포드 알고리즘을 수행 (시작 값 1)
음수 순환이 존재한다면 -1 을 출력 하고
아니면 2번째부터 n 번째 값을 출력 이때 dist[i]로 갈 수 없다면 -1출력
위 예시의 입력 값 을 넣어준다면 아래의 출력 값 이 출력 된다.
:)