Question

Juliet lives in a small town in Wisconsin called Verona. A stylized map of Verona is presented as a directed graph N(V, A) in Figure 1. The number on the arc represent the travel time incurred if traveling the corresponding piece of road. All roads are two-way streets and we assume that travel times are equal in both directions. 4 Figure 1: Network representation of Verona, WI Juliet has been invited to an exciting party, where she knows she will run into Romeo, her high-school sweet-heart. Juliet's house is located at vertex 1 of N(V, A). The party is located at vertex 10 of N(V,A). Juliet has volunteered to bring drinks to the party and needs to stop by a liquor store on her way. We will assume that she will be in and out of the store in a flash, and therefore, her time in store can be ignored. Verona has two liquor stores, which are located at vertices 4 and 6 of NV, A). Thus, starting from nodes, Juliet will need to choose a liquor store (vertex 4 or vertex 6), to make her way to that store, and from that store, to head to the party. Naturally, Juliet wants to get from her home to the party as quickly as possible. Help Juliet get to the party as fast as possible, by solving the following sub-problems. 1. Use one application of Dijkstra's algorithm to compute the shortest travel time from Juliet's place (vertex 1) to all liquor stores (vertex 4 and vertex 6). 2. Use one application of Dijkstra's algorithm to compute the shortest travel time from every liquor store (vertex 4 and vertex 6) to the party location (vertex 10). (Hint: We have seen in class that Dijkstra's algorithm finds shortest paths from the source to all vertices of the network. How can you use it to find shortest paths from all vertices to the sink? 3. Combine parts (1) and (2) to solve Juliet's problem, i.e., to find what her path to the party should be. 4. Your solution in part (3) uses two applications of Dijkstra's algorithm (one in part (1) and one in part (2).) Define a new network N' on 2n vertices and at most 2m + n arcs (and "appropriate" weights on these arcs), so that the original problem can be solved using a single application of Dijkstra's algorithm on N'.

Answer 1

4) Dijkstra’s shortest-path algorithm to compute the shortest path from “1” to all network nodes is as follows

Step D(4) P(4) D(5) P(5) D(6) P(6) D(7) P(7) D(8) P(8) D(9) P(9) D(10) P(10) D(3) P(3) 3,1(min) 3,1 3,1 Vertex/ D(1) P(1) Node 0 0,1 30,1 2 2 0,1 3 5 0,1 4 6 0,1 5 4 0,1 6 0,1 7 9 0,1 8 10 0,1 97 0,1 D(2) P(2) 5,1 5,1(min) 5,1 5,1 5,1 5,1 5,1 5,1 14(9+5),2 8(6+2),5 8,5(min) 3,1 3,1 3,1 3,1 3,1 3,1 3,1 8,5 6(3+3),3 6,3(min) 6,3 6,3 6,3 6,3 6,3 6,3 6,3 11(8+3),3 11(8+3),3 7(6+1),5(min) 7,5 7,5 7,5 7,5 8,5 8,5 8,5 8,5 15(8+7),4 15,4 15,4 15,4(min) 15,4 12(6+6),5 11(7+4), 9(8+1),4(min) 9,4 9,4 9,4 9,4 12(7+5),6 12,6 12,6(min) 12,6 12,6 12,6 14(9+5),8 14,8(min) 14,8 5,1 7,5 5,1 7,5 14,8

Step 0: Initially we take 1 as a minimum Weight and highlight that value
Step 1: In this we consider the minimum weight other than Node 1 that is at Node 3 we have minimum weight so highlight that value
Step 2: In this we consider the minimum weight other than Nodes 1 & 3 that is at Node 2 we have minimum weight so highlight that value
Step 3: In this we consider the minimum weight other than Node 1,2 & 3 that is at Node 5 we have minimum weight so highlight that value
Step 4: In this we consider the minimum weight other than Node 1,2,3 & 5 that is at Node 6 we have minimum weight so highlight that value
Step 5: In this we consider the minimum weight other than Node 1,2,3,5 & 6 that is at Node 4 we have minimum weight so highlight that value

Step 6: In this we consider the minimum weight other than Node 1,2,3,4,5 & 6 that is at Node 8 we have minimum weight so highlight that value

Step 7: In this we consider the minimum weight other than Node 1,2,3,4,5,6 & 8 that is at Node 9 we have minimum weight so highlight that value

Step 8: In this we consider the minimum weight other than Node 1,2,3,4,5,6,8 & 9 that is at Node 10 we have minimum weight so highlight that value

Step 9: In this we consider the minimum weight other than Node 1,2,3,4,5,6,8,9 & 10 that is at Node 7 we have minimum weight so highlight that value

Edge	1 - 2	1 - 3	1 - 4	1 - 5	1 - 6	1 - 7	1 - 8	1 - 9	1 - 10
Cost	5	3	8	6	7	15	9	12	14

The shortest path tree from the above routing table.

$1586030266109_blob.png$

1) Dijkstra's algorithm to compute the shortest travel time from Juliet's place (vertex 1) to all liquor stores (vertex 4 and vertex 6) is 8 and 7 respectively

2) Dijkstra's algorithm to compute the shortest travel time from every liquor store (vertex 4 and vertex 6) to the party location (vertex 10) is
from Vertex 4 to vertex 10 is 6 (4-8-10)
from Vertex 5 to vertex 10 is 9 (6-5-4-8-10)

3) Combine parts (1) and (2) to solve Juliet's problem, i.e., to find what her path to the party should be 10(1-3-5-4-8-10)