tags:

views:

36

answers:

1

The question is: Consider the directed graph with 5 vertices. Let the Dijkstra’s algorithm yield shortest paths from node s to all the other nodes, as shown in Fig. 1. Let the weight of the edge (x, t), increase and assume all nodes somehow obtain this information. How does node s modify Dijkstra’s algorithm to make minimum recomputations? Provide the final solution in the form “Node s runs Dijkstra’s algorithm by initializing S as and maintaining the list (< each node >) as .”

My question is... Isn't that a trick question because all it would do is increase the shortest path from s to t right?

alright so my picture isnt working

but it works something like this:

s->y->x->t

y also points to z. y->z

these are one way directional arrows.

+1  A: 

If (s,y), (y, z), (y, x), (x, t) are the only edges in this graph, then yes: this only increases the weight (or distance) of the shortest path of s to t, since there is only one such path.

Jan Gorzny
OH THANK YOU SO MUCH!!! I thought I was missing something.
Luron