Implementing Dijkstra's algorithm which is used to find single source shortest path in both directed and un-directed graphs and comparing performance when implemented with fibonacci, binomial and binary heaps.
Refer AA_report.pdf for dataset and implementation details
- g++ main.cpp fibo.cpp binomial.cpp binary.cpp
- ./a.out < input.txt
- g++ main.cpp my_binary.cpp
- ./a.out < ny.txt > output.txt
- Time taken to execute using fibonacci heap on input.txt - 0.126 msec.
- Time taken to execute using binomial heap on input.txt - 0.145 msec.
- Time taken to execute using binary heap on input.txt - 0.055 msec.
Detailed Results in AA_report.pdf We are able to show that for a small input graph dijkstra’s algorithm has provided performance boost when implemented using binary heap as compared to binomial and fibonacci heaps.