Question

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 P v∈P c(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 1

i presume that the student knows about the dijkstra algorithm for proper understanding of the question ,but still i have provided the basic operation of dijkstra algorithm in flow with the solution.