다익스트라 알고리즘 앞의 내용 요약
- (not R)파란 것 중에 파란 값이 가장 작은 것을 찾아 u라고 하자
- R집합에 u를 넣자
작은 순서대로 15넣고 17넣고 19넣고 20 넣으면 끝나는 거 아냐? ㄴㄴ
빨간 집합이 업데이트되었으므로(15노드 추가) 밖의 숫자들도 업데이트 해줘야 한다.
현재 dmin(u) = 15 (지금 들어간 값)
둘 중에 더 좋은 걸 집어넣어야 한다.(현재 값 or 지금 들어간 값+엣지의 weight)
즉,
원래 집합에서 가장 좋은 값(0,8,10집합에서 가장 가까운 17)
vs
(새로 추가된 노드를 포함한 0,8,10,15집합에서 가장 좋은 값)
다익스트라 알고리즘의 주장: 방금 추가된 노드와 연결된 노드만 업데이트하겠다
예를 들면 15와 인접한 17,19노드를 이렇게 업데이트!
근데 16보다 더 좋은 값이 있을 수 있는데 왜 저것만 보는가?
(방금 추가된 노드를 가장 마지막에 거치는 노드만 고려하기 때문이다.)
즉, 15를 중간에 거치는 길은 생각하지 않는다.
15를 중간에 거친다는 뜻은 15를 안거쳐도 된다는 뜻과 같음
shortest path는 모든 부분path가 shortest path이기 떄문에
여기까지 정확성 확인
이제 path의 길이를 통해 실제 path를 구해야 한다.
15노드가 추가되었다.
어떤 길인지 모르지만 17, 19짜리 길이 있다는 것을 알고있는 상태
17은 원래 있던 길이 더 좋은 상태
19는 15를 통해 오는 16짜리 길이 더 좋다.
19노드는 기억한다.
1. 나한테 오는 path의 길이는 16이다
2. 그 path에서 내 바로 앞에 있는 노드는 15노드라는 것을 기억
마찬가지로 모든 노드는 자기 직전 노드를 알고 있을 것이다.
직전 노드를 거꾸로 따라가면 source node가 나올 것이고 이것이 shortest path가 된다.
이건 Tree
shortest path가 여러개인 경우는?
17은 기존 path와 15를 통해 오는 path의 값이 똑같다.
17노드는 원래 17과 b노드를 기억하고 있었을 것이다.
그냥 추가적으로 b와 a를 모두 기억하면 된다. 작아지면 이전에 저장한 직전 노드를 지워버리면 됨.
DAG
Directed Acyclic Graph (방향성있고 사이클없는 그래프)