[Algorithm] What is Dijkstra's Algorithm?

1. Dijkstra's Algorithm 이란?

Dijkstra Algorithm 은 동적 프로그래밍을활용한 대표적인 최단 경로 탐색 Algorithm입니다. 이 알고리즘으로 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있습니다. Dijkstra Algorithm은 sequential algorithm이기에 MapReduce에 바로 적용하는 것은 불가능합니다. 왜냐하면 MapReduce에서는 데이터를 서로 주고받는 구조가 매우 힘들기 때문입니다. 그렇기에 MapReduce에서는 Brute-force 방식을 활용하여 모든 nodes를 다시 재 방문하여 구하는 식으로 사용하여 Dijkstra Algorithm을 MapReduce에 적용할 수 있습니다.

Figure 2.

Figure 2 같은 경우 Dijkstra algorithm을 Parallel BFS를 이용하여 MapReduce로 구현하였을 때의 psuedo 코드 이다. Map phase에서는 각 노드와 neighbor node와의 distance를 Emit 하고 Reduce phase에서는 그 중 min distance를 찾아 distance를 update 한 후 start node와 neighbor node 구조체를 emit 해준다. 

 

2. My Review

평소에 Dijkstra 알고리즘 자체는 코딩 문제를 풀면서 많이 접근한 적이 많은 친숙한 알고리즘이여서 쉽게 다가갈 수 있었다. 하지만 아무래도 여기서는 MapReduce에 Dijkstra 알고리즘을 적용해야 했어서 기존에 알고있던 방식으로는 사용할 수 없어서 조금 까다로웠다. MapReduce에서는 Parallel BFS를 활용하여 Dijkstra 알고리즘을 사용할 수 있었고 처음에는 까다로웠지만 전반적인 프로그램의 구조를 이해한 후에는 굉장히 유용한 구조임을 깨달을 수 있었다.