Consider the following problem: Design an algorithm to determine the best route
ID: 3877112 • Letter: C
Question
Consider the following problem: Design an algorithm to determine the best
route for a subway passenger to take from one designated station to another in a well-developed
subway system. Map the problem to a shortest path graph-problem. How do you construct the
graph for the following 3 cases. Indicate the meaning of vertices and edges. Draw a concrete
example.
1 The best route is the route that has the smallest number of stops.
2 The best route is the fastest route. Assume you know the time to travel between stops and
ignore the time spent in changing trains.
3 The best route is the fastest route considering also the time to change trains. How does your
graph account for the time of changing the train ?
Explanation / Answer
finds a shortest path tree from a single source node, by building a set of nodes that have
minimum distance from the source
vertices, or nodes, denoted in the algorithm by V or U ;
weighted edges that connect two nodes: (U,V) denotes an edge, and W(U,v)denotes its weight.
This is done by initializing three values:
dist,an array of distances from the source node S to each node in the graph, initialized
the way: dist(S) = 0;and for all other nodes V,dist(V) = . This is done at the beginning
because as the algorithm proceeds, the dist from the source to each node V in the graph
will be recalculated and finalized when the shortest distance to V is found.
Q, a queue of all nodes in the graph. At the end of the algorithm's progress, Q will be empty.
S, an empty set, to indicate which nodes the algorithm has visited. At the end of the
algorithm's run, S will contain all the nodes of the graph.
The algorithm proceeds as follows:
step:1 While Q is not empty, pop the node V, that is not already in S, from Q with the smallest
dist(V). In the first run, source node s will be chosen because dist(s) was initialized
to 0. In the next run, the next node with the smallest dist value is chosen.
step:2 Add node V to S, to indicate that V has been visited
step:3 Update dist values of adjacent nodes of the current node V as follows: for each
new adjacent node U,
if dist(v) + weight(U,V)<dist(U), there is a new minimal distance found for U ,
so update dist(U) to the new minimal distance value;
otherwise, no updates are made to dist(U).
The algorithm has visited all nodes in the graph and found the smallest distance to each node.
dist now contains the shortest path tree from source s.
CODE:
function suubwaysystem(Graph, source):
dist[source] := 0 // Distance from source to source is set to 0
for each vertex v in Graph: // Initializations
if v source
dist[v] := infinity // Unknown distance function from source to each node set to infinity
add v to Q // All nodes initially in Q
while Q is not empty: // The main loop
v := vertex in Q with min dist[v] // In the first run-through, this vertex is the source node
remove v from Q
for each neighbor u of v: // where neighbor u has not yet been removed from Q.
alt := dist[v] + length(v, u)
if alt < dist[u]: // A shorter path to u has been found
dist[u] := alt // Update distance of u
return dist[]
end function
}