단점 : 엄청나게 느리다.
해결하면 결국 다익스트라 알고리즘이 된다.
0인 애들이 우선마킹~
1 마킹~
2 마킹~
3 마킹~
4 마킹 ~ ~ ~
필요없는 계산을 줄일 수 있을까?
0 마킹~
1 마킹~
2 마킹~
3 마킹~
4 마킹~
5 마킹~
6 마킹~
7 마킹~
8 마킹~
새로 임의로 추가한 노드말고 기존 노드가 마킹 되는 곳
임의 추가 노드는 스킵한다면 실제 노드만 작업 할 수 있을 것이다.
0 -> 3 알 수 있을까?
다음 번 의미 있는 라운드는 3번 더 감 , 6번 더 감 알 수 있다!
먼저나오는 것부터 해야하니까 당연히 3!
3을 마킹하면서 3+9 =12가 고려대상으로 들어간다.
당연히 6이 작으므로 6먼저!
6을 마킹하면서 6+4=10 & 6+2=8 들어간다.
의미 있는 라운드들을 넣고, 가장 작은 애부터 꺼낸다.
가까운 노드부터 넣자. 라는 작전에서도 다익스트라 알고리즘을 만들어낼 수 있다.
다익스트라 알고리즘을 돌리면서 언제든지
Any Red Value <= Any Blue Value
값이 업데이트가 안된다면 당연히 red보다 클 것이고 (블루 중 가장 작은 값이 레드가 됐으니까)
값이 없데이트가 되더라도 x+?로 업데이트된다.
작전: 가까운 것부터 집어넣자
빨간애들은 재귀적으로 답을 아는 상태~
다음 노드가 뭔지 모르겠지만 남은 노드 중에 값이 가장 작은 거! = x라고 하자
파란 노드 중 가장 작은 노드를 찾아야 한다.
s -> x까지 가는 shortest path 중에 파란 노드가 가능한가?
NO! 결국 빨간 노드와 direct로 연결된 애들 중 가장 작은 애 찾는 것
프림과 다익스트라의 차이
이미 연결된 노드는 나중에 딴 게 나와도 무시한다.
프림알고리즘과 다익스트라의 무시하는 이유는 다르다.
alg 04 01 02 33:00~ (귀찮아서 캡쳐안함)
프림은 이미 들어간 노드들과 인접한 것 중 weight가 가장 작은 것을 넣는다.
= edge value가 가장 작은 것을 넣음
다익스트라는
source node과 인접한 것이 고려대상. => 값이 source+엣지의 값이 된다.
= 이전 노드+edge value가 가장 작은 것을 넣음
'알고리즘' 카테고리의 다른 글
알고리즘9 (0) | 2020.10.02 |
---|---|
알고리즘8 Deadline Scheduling (0) | 2020.09.27 |
알고리즘7 다익스트라, BFS (0) | 2020.09.23 |
알고리즘6 Djikstra Algorithm (0) | 2020.09.17 |
알고리즘5 - Kruskal Algorithm (0) | 2020.09.16 |