• 그래프에서 최단 거리를 구하는 알고리즘

• 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음 | O(VE) |

핵심 이론

1. 에지 리스트로 그래프를 구현하고 최단 경로 리스트로 초기화

• 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현
• 출발 노드는 0, 나머지 노드는 무한대로 초기화

2. 모든 에지를 확인해 정답 리스트 업데이트

• 최단 거리 리스트에서 업데이트 반복 횟수는 노드 개수 -1
  • 노드 개수가 N이고, 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N-1이기 때문
• 업데이트 반복 횟수가 K번이라면 해당 시점에 정답 리스트의 값은 시작점에서 K개의 에지를 사용했을 때 각 노드에 대한 최단 거리
• 업데이트 조건과 방법
  • D[s] ≠ ∞이며 D[e] > D[s] + w일 때 D[e] = D[s] + w로 리스트의 값을 업데이트

• 완성 후 이 그래프에 음수 사이클이 존재하는지 확인해야함

3. 음수 사이클 유무 확인

• 모든 에지를 한 번식 다시 사용해 업데이트되는 노드가 발생하는지 확인
• 업데이트되는 노드가 있다면 → 음수 사이클이 있다는 뜻
  • 2단계에서 도출한 정답 리스트가 무의미하고 최단 거리를 찾을 수 없는 그래프라는 뜻
  • 음수 사이클이 존재하면 이 사이클을 무한하게 돌수록 가중치가 계속 감소하므로 최단 거리를 구할 수 없음