50.1K

Verified Solution

Link Copied!

2. Fun story: Professor Shindler's ICS 46 class from Fall 2019 had a final on Friday the 13th. In Fall quarters, this problem set gets posted on or around October 31, Halloween. There exists a haunted maze which contains n scare stations, with a designated starting station s and a final station t. To model the haunted maze as a graph, there is a vertex for each scare station and a directed edge from one station to another if it is easy to walk between the two directly (note: because the owners of the haunted house place a restriction on which houses you can visit, the edge between the two scare stations is not bidirectional). Each scare station v has a scare factor of c(v), where the higher c(v) is, the scarier the scare stations are. Thus the graph has costs on the vertices rather than the edges. Shindler is a scaredy-cat, and wants to complete the maze by minimizing the total scare factor of the houses; in other words, he wants to find a path P from s to t such that Luepc(v) is minimum. Suppose you already have Dijkstra's Algorithm implemented for directed graphs. Describe how you can use that implementation to solve this problem For credit, your answer must involve creating a set of edge weights for the same set of vertices and edges such that a call to Dijkstra's algorithm will produce the desired tree. Do not re-create a Dijkstra-like algorithm

Answer & Explanation Solved by verified expert

See Answer