Sign In Sign Up Ask an AI advisor
TravisI00
TravisI00
07.07.2020 • 
Computers and Technology

Dijkstraâs single-source shortest-paths (SSSP) algorithm on a directed graph uses a set S that initially contains only the source s 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 d[v] value of a vertex v in V â S changes due to an update (line 5(c)A of the Dijkstraâs algorithm pseudocode). 1. Can the d[v] value of a vertex v in V â S 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 v ? 3. Can N(v) be less than the in-degree of v ? 4. If (v, w) is the lowest weighted edge in the graph, is it true that v must be added to S before w is added to S ? 5. Let the vertex v 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 v 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 S or in V â S? Why?

Solved
Show answers

Ask an AI advisor a question

I want advice