최단 경로(벨만-포드) 문제 솔루션

[1. 개요]

시간 복잡도 O(VE)

 

 

모든 Edge 의 relax 를 |V| 번 만큼 반복,

마지막 |V| 번째에서 relax 가 발생한다면, 음수 사이클이 있다는 것이다.

 

함정

• 벨만-포드 수행 후 어떤 노드 u 까지 가는 경로가 존재하는가?
• upper[u] != INF 가 아니라고 판단하면 안된다.
• 그래프가 아래와 같이, 완전히 연결되지 않았다면, 시작점과 연결되지 않은 상태에서, 음수 사이클이 있다면,
• 적당히 큰 값 M 에 대한 어떤 연산 결과가 참이라면 u 까지 가는 경로가 있다고 판단해야함.
  => 이 값은 문제 조건에 따라 다름...
  => weight 조건이 [0, K] 이고 (음수 weight 와 별개로.. 양수 weight 에 대해서만),
  => 전체 edge 개수가, L 개라면, 
  => M=KL 로 설정(?)

 

경로 복원

• 각 정점을 마지막으로 relax 시킨 간선만 모은다.
• => 스패닝 트리 형성
• 최단 경로는 이 트리 내 edge 로만 구성된다.

 

사용 패턴

• 음수 weight 가 있다
• 간단히 시간 복잡도 계산해서 시간내 가능할 것 같다면,

 

---

[2. 예제]

• https://testkernelv2.tistory.com/489
• b
• c
• d
• e
• f