주변에서 곡소리가 나온다. 다익스트라가 뭔지 도통 모르겠다는 사람들이 많다.
그래서 이악물고 다익스트라를 먼저 공부하기로 했다...
다익스트라 알고리즘
네델란드 박사님이 만든 알고리즘이다.
떨어져 있는 두 노드 사이를 갈 수 있는 가중치가 가장 작은 경로를 찾는것이다.
그냥 톨게이트 비용 가장 적게 내고 고속도로 탄다고 생각하면 된다.
우선은 모든 경로 간의 거리를 무한으로 한다.
우리는 최소값을 찾는 알고리즘이기 때문에, 0으로 설정해놓으면 오류가 날 것이다.
1번에서 출발을 하기위에 1번노드를 선택한다.
1번에서 1번으로 가는 비용은 없기에 노드1까지의 거리는 0이다.
1번을 선택했으니 1번에서 갈 수 있는 노드까지 가는 거리를 계산한다.
1번에서 2번으로 가는 거리는 2, 1번에서 4번으로 가는 거리는 1이다.
이때, 원래 숫자는 무한이었고, 무한과 2,1을 비교하면 2랑 1이 더 작다,
그러니까 갱신하게 되면
1에서 2로가는 최소거리는 2, 1에서 4로가는 최소거리는 1이다.
다음은 4번을 선택한다.
4에서 2로가는 최솟값은 2+1이기 때문에 3,
4에서 5로가는 최솟값은 1+1이기 때문에 2이다.
여기서 더하는 숫자는 N번까지 오는 거리 + N번에서 가는 거리 이다.
1에서 4로 가는 거리는 2였음으로, 계산한 후 최솟값을 갱신한다.
2를 선택한 후, 똑같은 방법으로 반복한다.
2까지 가는 최소거리는 2
2에서 3으로 가는 거리는 3
2에서 4로 가는 거리는 2
그러니까 1에서 3까지 가는 거리는 5, 1에서 4까지 가는 거리는 4이다.
근데 1에서 4까지 가는 거리는 원래 1이었음으로, 더 작은수인 1을 바꾸지 않는다.
쭉쭉 같은방법으로 진행하고
원래는 3번도 계산해야되지만
직관적으로 3을 거쳐가는건 숫자가 커지니까 과감하게 생략한다.
크루스칼
최소 신장 트리를 검색하면 나오는 2가지 알고리즘 중 하나인 크루스칼 알고리즘이다.
크루스칼은 다음과 같은 과정을 거친다.
- 크기가 작은 간선부터 모든 간선을 살핀다. 간선은 가중치에 정렬되어 있다. 즉, 가중치가 작은 간선부터 가중치가 큰 간선 순으로 정렬되어 있다.
- union-find 알고리즘을 통해 MST에 사이클이 생기지 않게 연결한다.
이게 뭔 소린가 싶다.
간단하게 말해서, 모든 노드를 연결하고 싶은데, 선을 노드-1개만 쓴다는 소리다.
MST는 최소 신장트리의 약자인데, 우리가 구하는 트리를 의미한다.
이래도 이해가 안되니까 예제를 보면서 알아보자.
다음 예제는 인터넷 뒤지다가 가장 깔끔하게 설명이 된 예제라 생각해서 글을 적어본다.
오른쪽에 있는게 가중치다.
v,w,Cost가 보인다.
쉽게 말하면
- v = 출발하는 노드의 숫자
- w = 도착하는 노드의 숫자
- Cost = 가중치
라고 보면 된다.
숫자를 잘 보면, Cost 기준으로 오름차순 정렬이 되어있는걸 볼 수 있다.
밑은 parent라고 나오는데, 각 노드들이 어디에 연결되어 있나를 알려주는 것이다.
일단 가장 위에 있는걸 추가해보자
( v , w , Cost) = ( 1 , 3 , 3 )이다.
이때, w가 3인데, 이는 parent의 3번을 보라는 뜻이다.
v가 1이기 때문에, parent 3 을 1로 바꾼다.
이는 ( v , w , Cost) = ( 1 , 3 , 3 )를 추가했을때,
1번 노드와 3번 노드가 같은 MST에 있다는 뜻이다.
( v , w , Cost) = ( 1 , 4 , 8 )을 추가하였다.
w가 4니까 parent 4를 보자, 4니까 v랑 같은 1이랑 바꿔주자.
여기서 잘 봐야 할게 parent 1,3,4가 1이 되었다.
이게 진짜 중요한거다
이 말은 즉 3번과 4번을 이으면 사이클이 생긴다는 뜻이다.
쉽게 말해서 1-3-4의 삼각형이 생긴다는 것이다.
위 설명 중에서
- union-find 알고리즘을 통해 MST에 사이클이 생기지 않게 연결한다.
라는것이 기억나는가?
union-find 알고리즘을 이용한다는 것은
v-w에 따른 parent 값을 바꿔 변화를 관찰한다는 것이고
MST에 사이클이 생기지 않게 연결한다는 것은
위에서 설명한 것처럼 삼각형이 생기게 하지 말라는 것이다.
다음걸 추가해주자. 지금 parent가 4라고 적혀있는데
저게 1로 바뀐다는 소리다. 지금 보면 5가 4로 바뀌는 것이 보이는가?
근데 4는 이미 1로 바뀌어 있다.
그렇기 때문에 5도 1로 바뀐다고 보면 된다.
이후
( v , w , Cost) = ( 1 , 2 , 10 )도 추가해주고
( v , w , Cost) = ( 2 , 3 , 13 )은 parent가 겹치기 때문에
사이클이 생기니까 추가 못하고
( v , w , Cost) = ( 2 , 5 , 14 )도 마찬가지로 사이클이 생기니까 추가 못한다.
크루스칼 알고리즘을 통해서 얻은 결과값은 이렇게 된다.
글로 보면 어려운데 예제가 너무 잘 나와있어서 한번에 이해되었다.
역시 velog랑 t스토리는 신이다
프림
이 방법은 우선순위 큐를 이용하는 방법이다.
크루스칼과 다른 점은
- 크루스칼은 Cost를 기준으로 오름차순 된 데이터를 넣는것이고
- 프림은 정점(V) 기준으로 오름차순 된 데이터를 절차에 따라 넣는것이다.
- 하지만 프림이 데이터를 넣는것은 크루스칼과는 다르게 우선순위 큐를 이용한다.
라고 일단 머리에 넣고 가면 되겠다.
자 일단 위 2개를 읽느라 머리가 빠질 것 같으니
여백의 미를 줘보자
잠시만 머리를 식히고 글을 보는걸 추천한다.
프림을 이애하는데 가장 중요한 부분이기 때문이다.
다음은 프림을 진행하는 순서이다.
- 우선 순위 큐에서 하나를 꺼낸다. 꺼낸 정점은 v라고 하자
- v가 MST에 포함되어 있다면, 1번으로 돌아간다.
- MST에 없다면, 연결된 간선을 모두 살핀다. w가 MST에 없다면 Cost 순으로 큐에 추가한다.
말로보면 뭔말인지 도통 이해가 안된다. 그러니까 그림을 보자
프림을 쓰기위해서 가져온 예시이다.
우선 왼쪽을 보면
- v - w 순으로 오름차순 되어있는 데이터가 보이고
- 오른쪽으로는 우선순위 큐가,
- 밑으로는 visit가 보인다.(이전에 parent와 같은역할이다.)
근데 visit는 T/F라는 것이 다르다.
먼저, 큐에는 (w,cost) = (1.0)(초기값)이 들어있다. 이걸 뽑아보자
v=1인 데이터를 우선순위 큐에 추가한다.
여기서 주의할 점은, 큐에는 w,cost 데이터만 추가되며,
Cost 기준으로 오름차순 되어 있다.
- 진짜 중요하니까 무조건 이해하고 넘어가야된다.
w가 1인 초기값을 뽑았음으로, visit는 1이 T로 바뀌게 된다.
(w,cost) = (3, 3)인 첫번째 큐 데이터를 뽑았다.
- visit[3] = T 가 되었고,
- v = 3 인 데이터 2개가 우선순위 큐에 추가되었다.
아니, (w,cost) = (1 , 3) 인 데이터는 추가 안했는데?
라고 물어볼 수 있지만, 밑을 보면
- visit[1] = T 이기 때문에 w = 1인 데이터는 추가를 안하는거다
- 이거 중요하니까 꼭 이해하고 넘어가자
거기다가 데이터를 추가할때도, cost순으로 오름차순해서 추가한다.
(w,cost) = (2 , 13)인 데이터는 cost가 가장 크기 때문에 제일 마지막에 추가한다.
똑같은 방법으로 데이터를 추가하자
w = 1 인 데이터는 추가 안하고
(w , cost) = (5 , 9 )인 데이터는 우선순위 큐에서. cost가 가장 적으니까 제일 위에 추가한다.
visit[4]를 바꾸는것도 잊지말자
위와 같은 방법으로 쭉쭉 해나간다
이후 visit가 꽉 찼음으로, 이 뒤의 큐는 모두 버려도 된다.
visit[2]는 이미 T니까 버리고
큐를 모두 소비하게 되었다.
이렇게 프림 알고리즘을 통해서 구한 결과값은 이렇게 된다.
