다익스트라 알고리즘

어떤 임의의 정점에서 출발하여 특정정점까지(정확히 말하자면 1 : N) 의 최단경로를 구하는 다익스트라 알고리즘에 대해서 포스팅 해보겠습니다.

다익스트라 알고리즘을 구현해 본 후에 제가 느낀 이슈 3가지에 대해서 살펴보겠습니다.

1. 그리디 알고리즘

2. 우선순위 큐를 써야하는 이유(꼭 써야하는건 아닙니다)

3. 메모이제이션

1. 그리디 알고리즘

다익스트라 알고리즘의 의사코드를 보면 '그리디하다' 라는것을 느낄 수 있습니다. 그리고 실제 구현할때 그리디하게(매순간 가장짧은경로를 취하는)하지 않으면 최단경로를 구하기가 매우 어렵습니다. 

2. 우선순위 큐를 써야하는 이유

많은 정보글에서 우선순위큐를 쓰면 좋다고 이야기들 합니다. 구현 중간에 '도대채 왜 써야하지?' 라는 의문이 들어서 우선순위 큐가 아닌 스택으로 한번 이미징을 해보니 '아! 이래서 쓰는거구나. 그리디하게 하기위해서! ' 이말에 대해서 부연설명을 해보면, 다익스트라 알고리즘의 핵심은 각 정점까지의 거리를 계속해서 '업데이트' 하는 것 입니다. 그런데 우선순위큐가 아닌 스택을 쓴다면, 제때제때 '업데이트'의 기회를 놓치게 됩니다. 그래서 일반적인 DFS나 BFS처럼 한번 방문했던 노드는 다시 방문하지않는 탐색으로는 이를 커버 할 수 없습니다.(단, DFS나 BFS의 코드그대로를 쓰기보다는, 조금수정해서 재방문할수있도록하면됨) 왜냐하면 다익스트라 알고리즘은 방문했던 노드도 다시 재방문때에는 거리가 '업데이트' 되기를 바라는 알고리즘이기 때문입니다. 따라서 우선순위큐가 다익스트라 알고리즘과 프림알고리즘에 prerequisite 라고 볼 수 있습니다. 하지만, 힙을 쓰기 싫다면, 매 루프마다 가장작은 가중치를 갖는 간선을 뽑아서 사용하는 식으로 커버 할 수 있습니다.

3. 메모이제이션

위에서 말햇듯이, 다익스트라 알고리즘의 가장 핵심 로직인 '거리 업데이트'에 대해서 사실 메모이제이션 기법이 들어갑니다.

모든 경로가 비교 될때마다, 기존에있던 경로 값이 더크다면 업데이트 되어야하며, 이런 로직이 돌아가기위해서는 경로값을 저장하고있는 배열이 필요하며, 초기에는 INFINITY(무한대)값으로 초기화가 되어야 다른 부가적인 코드없이 루프가 깔끔하게 돌아가게 됩니다.

그래프가 복잡해질수록(정점도 많아지고 경로도 많아진다면) 메모이제이션이 큰 힘을 발휘 하지 않을까 싶습니다.

 

Happy new year!

Keep going to ur goal.

I will also support what u wanna do.

Thanks giving new year which be can start awesome things.