다익스트라, 벨만포드, SPFA

https://www.acmicpc.net/board/view/40701#post

[벨만 포드]

1. 어떤 노드를 방문했는지 따지지 않음.

2. 모든 정점을 방문해서 거리를 갱신해야되기 때문임.

3. dist[here] != INF 조건은 필요함.(시작점에서 here까지의 길이 없고, 시작점→here→next까지의 거리가 갱신되버리기 때문임)

[SPFA]

1. queue와 inQ 배열에는 시작점에서 here까지 길이 존재해야 queue에 here이 push 될 수 있기 때문에

dist[here] != INF 조건이 필요하지 않음.

2. 기본 원리는 벨만 포드이기 때문에 방문 했는지 안 했는지는 중요 하지 않음.

3. 벨만 포드와 마찬가지로 작은 값이 들어올 수 있기 때문에 계속 갱신해야 됨.

[다익스트라]

1. 이미 갱신된 정점에 대해서는 출발점에서 그 노드까지의 최소 비용이 보장된 상태이기

때문에 방문 처리를 해야함.