Skip to content

Latest commit

 

History

History
17 lines (12 loc) · 1.16 KB

File metadata and controls

17 lines (12 loc) · 1.16 KB

Shortest_Path_and_Minimum_Spanning_Tree

This project was my 3rd Homework for the course CMPE 250 (Data Structures and Algorithms) at Bogazici University.

About the Project

This project was about 'Shortest Path' and 'Minimum Spanning Tree' problems. I implemented Dijkstra's Algorithm for shortest path and Prim's Algorithm for minimum spanning tree. I mainly used HashMap in order to have constant (theta (1)) complexity for accessing the data. This approach made my project efficient; but with the usage of just two dimensional arrays, I could have had the best efficiency. Detailed story about the project and the input/output formats can be found in the description.

Important Note: In very large input cases, as well as some small ones, there may be several different shortest paths; thus the answer would depend on the some implementation choices of the Dijkstra's algorithm. (There would be several correct answers.)

To Run the Code

First compile using: javac CMPE250_HW3_volcaniqueo/src/*.java -d CMPE250_HW3_volcaniqueo/bin

Then move onto bin: cd CMPE250_HW3_volcaniqueo/bin

Finally run using arguments: java project3main <input_file> <output_file>