BOJ 백준온라인져지 1865 웜홀 풀이

다익스트라 알고리즘과 차이점

1. 음수 가중치가 있어도 작동이 된다.

2. 음수 사이클을 체크할 수 있다.

내가 작성한 코드의 worst time complexity 예상 O(V^2*E)

작동방식

1. distance 를 모두 임의의 값으로 체운다.

2. edge 에 가중치들을 넣는다.

3. vertex 만큼 forloop 을 하나 돌린다.

4. 그 안에서 연결된 edge 를 다 체크해준다.

5. cnt 가 N 이 된다는 것은 update 가 된다는 뜻 ( 음수 사이클 )