Skip to content

hinammehra/MissionPopulate

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Mission Populate

Problem : Give a list of minimum school sites to be built such that at least one school is within 1Km of every house.

Solution : The program takes an input file which defines a connected graph of house and school vertices. After graph validation, a set is made for each school containing house vertices within 1Km of the school using Dijkstra's SSSP implementing the heap module. Then, set cover is used to output a minimum number of sets such that it covers all houses. The solution is the school vertex corresponding to the selected sets.

About

Determines the ideal location to put schools in a given city based on the locations of houses. Uses the greedy version of Dijkstra's shortest path first algorithm implemented using data structures such as heaps, adjacency list representation of a graph and set cover.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

 
 
 

Contributors