1. (Worth: 2 points. Page limit: 1 sheet; 2 sides) During thanksgiving break Ali
ID: 3729897 • Letter: 1
Question
1. (Worth: 2 points. Page limit: 1 sheet; 2 sides) During thanksgiving break Alice is planning to make a road trip from Madison to Seattle, and wants to stop at various tourist locations along the way for sight-seeing. The locations are numbered from 1 through n with n being Seattle, and this is the order that Alice wants to visit them in. Furthermore, since she has a limited amount of time for the trip, she wants to spend no more than hours driving Your goal is to help Alice plan her trip. You are given a directed graph over locations with each edge between two locations specifying the amount of time it takes to drive from one to the other. Design an algorithm that returns a path from Madison to Seattle with total driving timeExplanation / Answer
solution -
The algorithm use will be Dijkstra's shortest path algorithm as problem is asking to find out shortest path after analyzing the algorithm
User has to maintain vertices in two sets. One set of vertices will not be included in shortest path and other will set of vertices will be included
1. One set say setONE set, which contains vertices included in the shortest path.
2. Initially assign values to all vertices, initially assigning them as infinite except the source. source will be 0.
3. While setONE doesn't include all the vertices
a. Pick a vertex vtx1 which is not present in the setONE set and has minimum distance.
b. include vtx1 to setONE set.
c. Update distance value of all adjacent vertices of vtx1.
(For updating the distance values, iterate through all adjacent vertices. For every adjacent vertex vtx2, if the sum of distance value of vtx1 (from source) and weight of edge vtx1-vtx2, is less than the distance value of vtx2, then update the distance value of vtx2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.