Tarzan was spending a peaceful day in the jungle when his friend Jojo the chimpa

Question

Tarzan was spending a peaceful day in the jungle when his friend Jojo the chimpanzee began taunting him. You can't catch me, ape-man," shouted Jojo. Tarzan, always one to enjoy a good chase, began swinging after him, only to nd that Jojo had tangled up all of the hanging tree vines. Therefore, as Tarzan swings through the jungle, he can only move in the direction of the arrow in the square at the beginning of each swing. And because of the length of the vines, each swing must carry him exactly three or four squares.

Tarzan begins on the square at the top. From there he can travel three squares to A or go four squares to B. Suppose he goes to square B. On the next turn he can only go three squares (from B it is impossible to travel four squares). From square C he can go three squares to D or four squares to E.

Jojo has hidden in the square at the bottom of the maze of vines. How can Tarzan get to that square? (Note that only one square, the one marked F, will enable Tarzan to swing onto Jojo's square.

What type of graph algorithm would you use to model the problem and how would you construct this graph in code/pseudocode? (I.e., what do the vertices, edges, etc., correspond to?)

What algorithm will you use to solve the problem? Be sure to describe not just the general algorithm you will use, but how you will identify the sequence of moves Tarzan must take in
order to reach the goal.

Explanation / Answer

What type of graph algorithm would you use to model the problem and how would you construct this graph in code/pseudocode?

What algorithm will you use to solve the problem?

In my point of view tarzan should use Dijkstra's algorithm.

You can work it backwards as if your destination is your starting vertex. This will give you the distance and path to any other node.

We need to understand that we need to reverse the edges before applying Dijkstra with your destination as your starting vertex in order for that to work.

Dijkstra's algorithm works by marking one vertex at a time as it discovers a shortest path to that vertex.

Initially we mark just the vertex s since we know its (trivial) shortest path from source.

For your understanding I will explain you a scenario.

Consider the shortest path from source to some vertex x. It traverses a sequence of vertices, with a final vertex v that then connects to x to finish the shortest path to w.

The key observation is that the path up to v must be a shortest path to v.

Because if it weren't, we could replace that path to v with a shorter path, which would also shorten the path to w, which would contradict the claim that we have a shortest path to w.

So suppose you've marked some set of vertices M. There is apath called next path followed by traversing a single edge from v to some vertex w not in M.

so let w be the closest vertex to s that is not in M. As we just argued, the shortest path to w goes through a sequence of vertices with some vertex v just before M. But that means that v is closer to s than w is, which means that v is marked. And that means that the shortest path to w is in fact the next path to w through v. This tells us how to grow our set of marked vertices.

Dijkstra figured out a particularly efficient way to implement the abstract algorithm I just described.

Relying on this invariant, we can implement the algorithm. We store the labels in a priority queue. This makes it possible for us to update labels when we need to, and also lets us extract the minimum label when we need it. Whenever we extract the minimum label vertex w, we know its shortest path so can add it to M. Then we update all the exit paths from w.

Some quick steps to make it efficient.

-remove the entry with earliest time

-add a new entry (this happens up to once for each node),

- decrease time with already which is available there.

Steps of Dijktra algorithm

-Consider all nodes. For initial node set tentatative distance as zero and others as infinity

-Set the initial node as current. Mark all other nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.

-Calculate tentative distances.

- when we got through the node check node as visited so that we should not need to visit again

- unvisited node set is infinity then stop

- select unvisited node which has small tentatative distance consider as new node and call back the third step again.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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