11657

• distance범위주의
• distance는 최대 몇인지를 잘 모르겠다.
• 최대가아니라 최솟값을 주의해야한다
• 음의사이클을 돌면서 distance가 계속해서 감소한다
• 간선이 최대 6000개 있을 경우에 한 노드는 그 간선6000개 때문에 6000번의 업데이트를 가지게 될 수있다. 그런데 -10000만큼 작아진다면
  6000-10000만큼 작아질것이고 이것을 매라운드(n-1)마다 반복하니까
  6000 -10000 * (500-1)만큼 작아질수있기때문에 int가 아니라 long으로 선언해주어야한다

 public static boolean Bellmanford(int start){
        distance[start] = 0;
        //v-1번만 반복을 한다. i번의 반복을 할때마다 1번의 간선만 거친경우, 2번의 간선만거친경우.. (가장먼거리의노드에겐)v-1번의 간선만 거친 경우에 대해서
        //distance를 도출해낸다 그렇기때문에 v-1번반복을 해야한다
        for(int i=0;i<v-1;i++){
            //모든 간선에 대해 조사한다
            for (Node node:list){
                //inf가 아니라는것은 이미 방문한적이있는 노드라는것이고, 그 경우에 한해서 node.e를 갱신해준다
                if(distance[node.s]!=INF && distance[node.e] > distance[node.s] +  node.cost){
                    distance[node.e] = distance[node.s] + node.cost;
                }
            }
        }

        //만약에 위의과정을 거쳐서 최단경로를 확정지었는데도 계쏙갱신이 되는곳이있다면
        //그 그래프는 음의 사이클을 가진다고볼수있다. 그렇기에 최단경로를 구할수없음을 표시해준다
        for (Node node:list){
            if(distance[node.s]!=INF && distance[node.e] > distance[node.s] +  node.cost){
                distance[node.e] = distance[node.s] + node.cost;
                return true;
            }
        }
        return false;
    }

22865

• 
• 위사진에 있는 코드를 아래사진과같이 바꿔도 정답이 뜨는데 그 이유를 모르겠다
  
• distance[p.to] -> p.cost 로바꿨다

의문1

• p.cost < distance[p.to]라면 distance[p.to]를 p.cost로 갱신해야하는거아닌가? 생각해보니 왜 갱신하는코드가 없을까?

의문2

• 왜 코드를 바꿔도 정답이 뜨는걸까? 둘은 일치하지않을때도있는데말이다.
  예를들면 큐에 집어너호 나서 distance가 업데이트된다면 cost와 distance의 값은 달라지게된다.

1719

• https://lotuslee.tistory.com/99
• a->b->c->d면
  distance[a][b]=b;
  distance[a][c] = distance[a][b],
  distance[a][d] = distance[a][c]
  이런식으로가면 결국 a-d, a-c, a-b에 모두 b가 저장됨