저도 몰라서 찾아봤는데 왜 한 번이라도 업데이트 된 정점만 계산해야 되는지는 아래 블로그에 잘 나와있네요

https://yabmoons.tistory.com/3...

요약하면 upper[here]가 INF면 시작정점(1번정점)에서 here로 가는 경로가 아직 없다는 뜻이기 때문에 업데이트하면 안 되는 것 같습니다.

upper[here]가 업데이트가 되면 아직 경로가 없는데도 INF가 아니게 됩니다.

밸만 포드는 특정 정점을 시작점으로 두고 시작합니다. 이 문제에서는 1번 정점이죠.

그리고 모든 간선 정보를 순회합니다. 이때 dist[간선의 시작점] = INF인 곳은 고려하지 않습니다.

이 방법 덕분에 처음에 설정한 [시작 정점]과 간선의 [시작 정점]이 같은 정보들부터 고려하게 됩니다.

즉 처음에 설정한 시작 정점과 연관된(연결된) 간선들만 계속해서 고려할 수 있게 됩니다.

그럼 결과적으로 문제에서 요구하는 1번 정점으로부터 모든 정점까지의 거리를 구할 수 있습니다.

연관되어 있지 않은 간선도 고려하는 알고리즘으로는 플루이드 와샬이 있습니다. 

그래서 플루이드 와샬은 특정 정점이 아닌 모든 정점에서 모든 정점까지의 최단 거리를 구할 수 있구요.