Best suited graph algorithms for specific scenario
I have selected chosen the suitable algorithms for these situations but the question includes TO SPECIFY in terms of undirected or directed, and unweighted or weighted too! I am getting confused in that part. Can anyone help?
You have data for the rail transport (i.e. train track) network in London, including the
length of each section of track. You need to compute the shortest (in terms of distance) route
for a train travelling between cities.
Answer: Dijekstra algorithm
(b) You need to lay water lines for a new housing development (i.e. pipes to carry water to
and from each house). You have data on all the places it’s possible to build pipes, and how
much pipe would be required in each case. From the many potential pipeline options, you
must compute which pipes to build such that you use the least amount of pipe overall.
Answer : Prims algorithm
(c) You are compiling a program from source code and you know the dependencies between
source files (i.e. for each file F, you know which other files, if any, can’t be compiled until F
is compiled). You need to compute a valid compilation order such that each file is compiled
after all its dependencies are compiled.
Ans: Topological Sort
(d) You have data about friend relationships from a social network, and you want to model
the spread of a rumor based on these relationships. Your model is that a rumor starts with a
single person, who then tells all of their friends. Then at each subsequent step, everyone who
knows about the rumor spreads it to all of their friends who don’t know it. You want to
compute how many people know about the rumor after k steps.
Answer : Depth First Search
You have data for the rail transport (i.e. train track) network in London, including the
length of each section of track. You need to compute the shortest (in terms of distance) route
for a train travelling between cities.
Answer: Dijekstra algorithm
(b) You need to lay water lines for a new housing development (i.e. pipes to carry water to
and from each house). You have data on all the places it’s possible to build pipes, and how
much pipe would be required in each case. From the many potential pipeline options, you
must compute which pipes to build such that you use the least amount of pipe overall.
Answer : Prims algorithm
(c) You are compiling a program from source code and you know the dependencies between
source files (i.e. for each file F, you know which other files, if any, can’t be compiled until F
is compiled). You need to compute a valid compilation order such that each file is compiled
after all its dependencies are compiled.
Ans: Topological Sort
(d) You have data about friend relationships from a social network, and you want to model
the spread of a rumor based on these relationships. Your model is that a rumor starts with a
single person, who then tells all of their friends. Then at each subsequent step, everyone who
knows about the rumor spreads it to all of their friends who don’t know it. You want to
compute how many people know about the rumor after k steps.
Answer : Depth First Search
Topic archived. No new replies allowed.