Optimizing Time Per Subproblem: Understanding Indegree and Acyclic Dependencies

[evinda]

Hello! (Wave)

According to my lecture notes:

Suppose that we want to find the shortest path of a graph from $s$ to $v$ for some $s, v \in V$.

- Subproblem dependency should be acyclic.

#subproblems=$|V|$

time per subproblem: indegree $(v) $time= $\sum_{v \in V}$ indegree $(v)$+1=$\Theta(V+E)$

Why does it hold that [m]time per subproblem: indegree $(v)$[/m] ?

 

[Future Bruno]

The time per subproblem refers to the time required to process each vertex in the graph. Since the time required to process a vertex is determined by its indegree (the number of edges that are connected to it), the time per subproblem is the indegree of the vertex.