알고리즘7 다익스트라, BFS

지난번까지 다익스트라의 정확성에 대한 하나의 설명

 

---

 

직관을 위한 설명 추가

 

그 전에 먼저 코드로 바꾸자.

 

G를 입력으로 받아야 한다.

G = (V, E, g) (노드set, 엣지set, 엣지마다 weight)

 

방법은 여러개!

엣지 순서대로, weight 순서대로 줄 수도 있고

노드노드 weight, 노드노드 weight로 줄 수도 있겠지

 

처음에 source노드와 연결된 노드는 모두 블루 노드로!

 

처음에는 다 무한대로 셋팅

 

시작노드는 V0

벡터나 링크드 리스트로 따라가면서 초기치를 바꾼다.

 

(3,2)추가

 

 

Red set marking

처음에 하나만 확정

 

여기서 레드 노드가 추가될 때마다 하나씩 마킹해주면 됨

 

 

 

n-1번 반복

---

우선순위 큐를 쓰면 된다.

작은 것부터 나오는 큐

 

방금 추가된 노드와 직접 연결된 노드만 고려하자.

지금 엣지로 업데이트 된 값을 우선순위 큐에 넣고 가장 작은걸 빼자

 

큐에 넣을 때 가장 간단한 버전 (꺼낼때 귀찮은게 차라리 나음)

파란색 중에 Dmin을 찾아야 한다

 

새로 추가된 노드에 의해 업데이트

35

38

36이 된다.

 

이중에 35가 된 노드는 이미 빨간 노드이다

=> 원래 노드의 값이 35보다 작았을 것임

 

안 넣어도 되지만 그냥 큐에도 넣자. (P,35)

 

파랑 노드의 값이 이랬다면 ?

36 < 38 이니까 안넣어도 되지만 그냥 이것도 넣자 (Q,38)

 

저절로 파란 애 중에 작은 걸 찾게 된다.

 

 

큐에 뭐가 들어있을까?

Blue value와 Red value가 모두 들어있다.

동일한 노드가 여러개 있을 수 있다.

어쨌든 꺼내면 숫자가 작은거 부터 나온다.

red node가 나오면 이미 답이 확정된거니 더 좋은 답은 없다.

최초의 블루가 나오면 블루 중에 제일 작은 것!

 

---

성능?

전체적으로 보면 모든 엣지가 2번씩 사용 (2n) => O(n)

우선순위큐 log n 

 

= O(mlog n+n)

= O(mlog n)

 

 

 

=> 이렇게 있으면 구현할 수 있음!

 

 

 

---

---

BFS

 

BFS는 어떤 경우에 가장 성능이 좋다

=> 모든 엣지가 1일 때

 

 

모든 weight가 1이라고 가정한 그래프!

우선 순위 아닌 그냥 큐

mark배열 - source노드만 1로 마킹(방문했으니까)

distance배열 - source노드로부터의 거리(초기는 가비지값)

 

일단 큐에 s를 넣는다.

큐에서 순서대로 하나 꺼낸다. i

만약 i가 marked라면, 아무것도 하지 않는다.

아니라면, i를 mark한다 & i에 인접한 모든 노드 j에 대해서 (j,dist[i]+1)을 큐에 넣는다.

 

작은 것이 큐에 먼저들어간다고 증명해야 한다 (결국 우선순위 큐와 같음)

 

 

 

 

source가 큐에 들어갔다가 나오면 큐에 (1,1) (2,1) (3,1) (4,1) (5,1) 추가

순서대로 1,2,3,4,5노드가 사용될텐데

4번이 (5,2)를 넣고

5번이 (4,2)를 넣으려했지만 이미 마킹되어있으므로 무시되어 최종거리는 1

 

 

다익스트라와 같지만 큐에서 log가 빠진다

BFS = O(m+n)

 

weight가 1이 아닐때는? BFS로 바로 설명하려면?

그래프를 고친다

 

모든 엣지weight가 1인 그래프로 바꾼다. => 시간이 엄청걸린다

 

필요없는 계산이 있는지 생각해보자.