Dijkstra's single-source shortest-paths (SSSP) algorithm on a directed graph uses a set 5 that initially contains...

Transcribed Image Text:

Dijkstra's single-source shortest-paths (SSSP) algorithm on a directed graph uses a set 5 that initially contains only the sources and that eventually includes all the vertices of the graph. Vertices are added to S one at a time. Let N (v) denote the number of times that the div] value of a vertex v in V-S changes due to an update (line 5(c)A of the Dijkstra's algorithm pseudocode). Answer each of the following questions (provide a brief justification for each of your answers). 1 1. Can the d[v] value of a vertex u in V-8 ever get smaller than the cost of a shortest s-to-v path in the graph? 2. Can N(v) exceed the in-degree of u? (Recall that the in-degree of a vertex is the number of edges going into it.) 3. Can N(v) be less than the in-degree of v? 4. If (u, w) is the lowest weighted edge in the graph, is it true that u must be added to 5 before w is added to S? 5. Let the vertex u have the ith longest shortest-path from s to it, and assume that there is no tie for that ith rank (i.e., no vertex other than has that particular length of a shortest path from s to it). Suppose you are told that, at a given point during the execution of Dijkstra's algorithm, the size of S is j. Is this information sufficient to determine whether, at that point, v is in 5 or in V-S? Why? Dijkstra's single-source shortest-paths (SSSP) algorithm on a directed graph uses a set 5 that initially contains only the sources and that eventually includes all the vertices of the graph. Vertices are added to S one at a time. Let N (v) denote the number of times that the div] value of a vertex v in V-S changes due to an update (line 5(c)A of the Dijkstra's algorithm pseudocode). Answer each of the following questions (provide a brief justification for each of your answers). 1 1. Can the d[v] value of a vertex u in V-8 ever get smaller than the cost of a shortest s-to-v path in the graph? 2. Can N(v) exceed the in-degree of u? (Recall that the in-degree of a vertex is the number of edges going into it.) 3. Can N(v) be less than the in-degree of v? 4. If (u, w) is the lowest weighted edge in the graph, is it true that u must be added to 5 before w is added to S? 5. Let the vertex u have the ith longest shortest-path from s to it, and assume that there is no tie for that ith rank (i.e., no vertex other than has that particular length of a shortest path from s to it). Suppose you are told that, at a given point during the execution of Dijkstra's algorithm, the size of S is j. Is this information sufficient to determine whether, at that point, v is in 5 or in V-S? Why?

Answer rating: 100% (QA)

No the dv value of a vertex v in V S never get smaller value than the cost of a shortest stov path i... View the full answer