. During a friendly game of Mario Party, Daisy nds herself cast into a Tangled W

Question

. During a friendly game of Mario Party, Daisy nds herself cast into a Tangled Web minigame. The only way out is to reach one of the mushrooms, which, when consumed, will transport her to safety. Now in order to walk around in the Tangled Web, she must spend coins. Each link in the graph is marked with the cost to Daisy if she were to travel on it; to travel from D directly to Q, for instance (or vice versa) would cost her 1 coin. In case this isn’t clear from the diagram: Daisy begins at node D.
a. Which of the three mushrooms is the most sensible one for Daisy to go for, and how many coins will it cost her to reach it? Use Dijsktra’s shortest path algorithm to solve this problem. Your solution should include the following:

• A copy of the diagram, with your work from Dijkstra’s algorithm clearly and legibly shown. In particular, I should see arrowheads on edges, some of which have been erased, and numbers on each node, with as the rst entry, crossed out, with “better” entries to the right of the as they are discovered. I should also see the shortest path edges from D to the “best” mushroom darkened clearly with your pencil. • Separately, a list of the shortest paths from Daisy to each of the three mushrooms. For instance, “D—R—I—J—K—L—M2.” (I’m not saying that’s the correct answer for mushroom #2.)
b. As soon as Daisy eats the mushroom that transports her out of this maze, she pulls a fast one on Mario, and transports him into the maze, where he is forced to connect all the spaces together with rope in 30 seconds. Every inch of rope that he uses costs him coins, so he wants to be as ecient as possible with his connections. Assume that the cost of a rope between two nodes is the same as Daisy’s cost of traversing that edge. What’s the minimum amount of rope he could use to ensure that every node is directly or indirectly connected to every other node through a path of rope? Show the conguration of how he should lay out his rope, by using another printout of the diagram in which you clearly darken the chosen edges

Explanation / Answer

a.

M1 mushrooms is the most sensible one for Daisy to go.She spend 15 coins

shorest Path - D -> R -> I -> C -> A -> M1 = 15 coins

A.Below Given list of the shortest paths from Daisy to each of the three mushrooms.

D -> R -> I -> C -> A -> M1 = 15 coins

D -> Q -> P -> M3 = 16 coins

D -> R -> N -> M -> L -> M2 = 18 coins

B. Daisy eats the mushroom that transports her out of this maze.Here is minimum amount of rope he could use to ensure that every node is directly or indirectly connected to every other node through a path of rope.

M2 -> L -> M -> I -> C -> A -> M1 = 21 coins

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.