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

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

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

1. 모든 에지를 확인해 정답 배열 업데이트하기

• 최단 거리 배열에서 업데이트 반복 횟수는 노드 개수 - 1이다.
• 특정 에지 E = (s, e, w)에서 아래와 같은 조건을 만족하면 업데이트를 실행한다.
  • D[s] ≠ 무한대이며 D[e] > D[s] + w일 때 D[e] = D[s] + w로 배열의 값을 업데이트한다.

1. 음수 사이클 유무 확인하기

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