알고리즘7-2 BFS

단점 : 엄청나게 느리다.

해결하면 결국 다익스트라 알고리즘이 된다.

 

---

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가 가장 작은 것을 넣음