shortest path : 다익스트라.

두개의 Lemma 

1. 파란 애 중에 가장 작은 값이 정답이다.

=> 귀류법으로 증명하자. 

다른 파란애를 거치고 그 노드로 가는 path 만이 또 다른 답이다.

모순 발생! 파란 애들은 이미 "빨간 것만 거쳐 가는 가장 짧은 길의 길이"이므로 

파란애들끼리 거치면 더 커질 수 밖에 없다. 

 

2. 방금 들어온 노드로들만 update 하면 된다. 

=> 방금 들어온 노드가 중간에 끼어있는 path는 고려할 필요가 없다. 

----> path 업데이트는 파란 노드만 (빨간 것만 거쳐가는 경로 중에 가장 짧은) 취급함, 그러면 빨간 영역에서 거쳐가는 경로가 달라지는 경우만 고려한다는 의미임. 

-----> 하지만 (방금 들어온 노드가 중간에 끼인 path) 는 (방금 들어온 노드가 마지막인 path)보다 항상 크다. 

 

그러므로 방금 들어온 노드만 업데이트 하면 된다.