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.