[Project] Make Dijkstra program by using Hadoop

Goal of Program

주어진 Twitter graph dataset을 이용하여 shortest path length 구하기

 

Dijkstra

1st-MapReduce (Preprocess 과정)

1st Map : 주어진 Twitter datset의 형태를 key node는 start node로 value 는 neighbor node와 weight로 바꾼 후 Emit

1st Reduce : Map의 output 을 aggregate 할 시 key node에 따른 total number of neighbor node와 모든 (neighbor node, weight) 형태로 Emit

 

2nd-MapReduce (Iteration 과정)

2nd Map : 각 key node에 따라 neighbor node에 따른 새로운 distance(current distance + weight)를 구한 후 Emit 

2nd Reduce : Map의 output 을 aggregate 할 시 Key node에 따른 distance 들 중 가장 작은 distance를 찾은 후 새로운 min distance update하여 Emit

 

 

Used Language

Java

 

My Review

저번에 했던 PageRank 알고리즘을 활용하여 만들었던 MapReduce 프로그램과 비슷한 형태이여서 Dijkstra 알고리즘만 정확히 이해하고 있으면 구상하기 편했다. 또한 기존의 MapReduce 했던거와 다르게 Node를 구조체 형태로 만들어 사용하여 필요한 값들을 조금 더 편리하게 사용할 수 있어서 또 새로운 방법을 배울 수 있었다. 이것 또한 매 Iteration마다 정확히 내가 짠 알고리즘이 적용되는지 확인하기 위해서 Hadoop에서 제공하는 다양한 명령어들이나 file system을 이해해야 했기 때문에 좋은 기회가 되었다.

 

 

Project Code

https://github.com/guswns00123/Dijkstra.git

GitHub - guswns00123/Dijkstra

 

Interested Concept

What is Dijkstra algorithm?

https://guswns00123.tistory.com/20

[Algorithm] What is Dijkstra's Algorithm?