[CS] 다익스트라에 대한 나름의 이해

다익스트라에서 중요한 기준은 시작점이다. 모든 건 시작점을 기준으로 생각되어야 한다. 왜냐하면 시작점과 관계를 가지기 때문이다.

두번째 포인트는 현재 선택되어 있는 노드는 어떠한 경로로든 그 노드까지 가는게 그 순위라는 것이다. 예를 들어, 1번이 시작점이다. 그리고 차례대로 선택된 노드가 5, 2, 6번이라면 1번에서 5번으로 가는 길이 어떻게든 2번까지 가는 길보다 짧다는 것이다. 

세번째 포인트는 현재 선택되어 있는 노드는 아직 선택되지 않은 다른 어떤 노드보다 출발점부터 가는길이 짧다는 것이다. 

네번째 포인트는 선택되지 않은 노드는 두가지 선택점을 가진다는 것이다. 현재 선택된 노드에서 가는게 더 짧은 것인가 아니면 어떤 경로인지는 모르지만 최단 경로가 더 짧은 것이냐다. 일단 출발점에서 현재 선택된 노드에 가는 건 A 출발점에서 선택되지 않은 노드보다 가는 것 B보다 짧다.(같을 수도 있지만 이 경우는 제외한다). 그렇다면  A < B이다. 여기서 생각해보면 현재 선택된 노드에서 선택되지 않은 노드까지 가는 걸 C라고 해보자. 그렇다면 A + C는 출발점에서 선택된 노드를 거쳐 선택되지 않은 노드에 가는 것이다. 결국 출발점에서 선택되지 않은 노드를 가는 것이다. 그럼 A+C < B이라면 출발점에서 선택되지 않는 노드로 가는 최단 거리가 발견된 것이다. 따라서 여기서는 A+C와 B라는 두가지 선택지 중 A+C가 선택되고 최단 거리로 갱신이 될 것이다. 

하나 생각해볼 점은 선택된 노드는 일단 더 이상 최단 거리가 갱신되지 않는데 만약 선택되지 않은 노드와 연결했을 때 최단 거리가 될 수 있지 않느냐이다. 이걸 해결하기 위해 이렇게 생각해보자. 일단 현재 선택된 노드는 선택되지 않은 노드보다 짧다. 선택되지 않은 노드와 연결이 된다는 건 1번부터 어떻게든 선택되지 않은 노드로 연결되어 선택된 노드로 가는게 짧다는 건데 이건 말이 안된다. 왜냐하면 세번째 포인트로 인해 현재 1번부터 선택된 노드로 가는게 1번부터 선택되지 않은 노드로 가는 것보다 짧기 때문이다. 하지만 선택되지 않은 노드에서 선택된 노드로 가는건 무조건 0 이상이다. (마이너스가 되면 결과가 달라질 수 있다. 그래서 그때는 다익스트라를 못쓴다) 따라서 1번부터 선택되지 않은 노드를 거쳐서 선택된 노드를 가는건 1번부터 선택된 노드를 가는 것보다 길 수 밖에 없다.

Reference

---

https://hub1234.tistory.com/32 

다익스트라 알고리즘(최단 경로 알고리즘 )기본 개념 원리