벨만포드 - 최단거리

핵심 포인트

1. 간선정보가 핵심이므로 2차원 배열을 사용한다면 값이 덮어 씌어지지 않도록 조심한다.
2. 간선정보의 현재위치가 첫방문이라면 'continue'해야한다. 다익스트라 알고리즘과 최단거리 비교하는 방식이 비슷한데 간선정보만으로 최단거리를 업데이트하기 때문에 시작지점과 연결여부를 알아야한다면 첫방문 여부를 검사해야한다.
   https://www.acmicpc.net/problem/11657

  if visited[curr] == 0:
      continue
  if visited[next] != 0 and d[next] <= d[curr] + cost:
      continue

3. 시작지점과 목적지까지 연결여부가 상관없다면 현재 위치의 방문여부를 체크하지 않는다.
   https://www.acmicpc.net/problem/1865

4. 음수간선이 있을 때, 다익스트라는 Que가 소진될 때까지 무한루프를 돌지만 벨만포드는 m개의 간선을 n번만큼만 돈다.

5. 무한 사이클감지는 마지막 n번째 반복문에서 m개의 간선으로 최단거리 업데이트를 시도하고 성공했다면 무한 사이클로 판단할 수 있다.

6. 시작 지점과 도착 지점간에 무한 사이클이 있는지 검사하는 방법은 무한 사이클에 포함된 노드로 부터 bfs를 이용해서 도착지점에 사이클이 연결되는지 알 수 있다.

7. 최단거리 경로를 추적할 때 무한사이클이 경로에 없다면 유한한 순서를 구할 수 있다. bfs를 이용해서 시작지점부터 끝지점까지 더 나은 cost를 중점으로 탐색한다.