For each of the following scenarios decide which graph algor

For each of the following scenarios, decide which graph algorithms would be best to use: critical path analysis, unweighted shortest path, Dijkstra\'s, Kruskal\'s, Ford-Fulkerson, Articulations Points, or none of the above. a. Determine the number of people to assign to each job in a large project. b. Given a map of the power grid, the production of power plants, and the power consumption of the cities, determine how best to transfer electricity from one city to another to minimize the amount of electricity transferred within the country. c. Given a road map of a city, determine which bridges must be reinforced because they are the only way to get from some neighborhood to the rest of the city. d. Given the road map of a city, for each house in a city, determine their nearest and second nearest elementary school. e. Given the population of an endangered area, and a road map that include the number of people each road can carry in an hour, determine how long it would take to evacuate the area. f. Given blueprints that show the location of the main electrical panel and power outlets, design the wiring of a building to minimize the amount of wire used. g. It is 3 am and you are in Manhattan where all the blocks arc the same length, and have 25 mph speed limits, determine the quickest route to your destination. h. Given the seven recipes, determine the length of time for you to prepare a seven-course dinner. i. Given a map of all the blood vessels of the brain, determine how long it will take for blood entering from the carotid artery to reach every parts of the brain. j. Given a list of the times flights will arrive at an airport, and their fuel remaining when they arrive, provide an ordering of the flight landings than ensures all will land before they run out of fuel.

Solution

a.

None of the above.

b.

Kruskal’s algorithms.

Kruskal’s algorithms is the algorithm which is used to find the minimum cost spanning

tree in a graph. Here, this algorithm will work fine.

c.

Articulation points.

Articulation point is the point, by removing that point breaks the graph in the two

parts. Therefore, to reinforce the bridge use the Articulation point algorithm.

d.

Dijkstra’s Algorithm.

Dijkstra’s algorithm is used to find the shortest path from a source vertex to all the others

vertices. It also follows some sequence to find the shortest path one by one. Because it’s a

sequential algorithm, it will also tell the second nearest elementary school.

e.

Ford-Fulkerson,

Ford-Fulkerson is used to find the flow of the graph. It means in this from source

vertex to the destination vertices its traverse all the edges and covers all the way of

reaching the destination.

f.

Kruskal’s algorithms.

Kruskal’s algorithms is the algorithm which is used to find the minimum cost spanning

tree in a graph. Here, this algorithm will work fine.

g.

Unweighted shortest path.

This algorithm is used to find the shortest path between the two vertices in a graph which

has the same length. And it is faster than Dijkstra’s algorithm.

h.

Critical Path Analysis.

Critical path identification is required for any project-planning phase. This gives the project

management the correct completion date of the overall project and the flexibility to float

activities.

i.

Dijkstra’s Algorithm.

Dijkstra’s algorithm is used to find the shortest path from a source vertex to all the others

vertices. It also follows some sequence to find the shortest path one by one. Because it’s a

sequential algorithm, it will also tell the second nearest elementary school.

j.

Ford-Fulkerson,

Ford-Fulkerson is used to find the flow of the graph. It means in this from source

vertex to the destination vertices its traverse all the edges and covers all the way of

reaching the destination.