# Question

Let G = (V, E) be a weighted, directed graph with weight function w: E → {0, 1, ..., W } for some nonnegative integer W . Modify Dijkstra' s algorithm to compute the shortest paths from a given source vertex s in O(W V + E) time.

## Answer to relevant Questions

Modify your algorithm from Exercise 24.3-6 to run in O ((V + E) lg W ) time. (Hint: How many distinct shortest-path estimates can there be in V - S at any point in time?)As it appears above, the Floyd-War shall algorithm requires Θ (n3) space, since we compute for d (k) i, j, k = 1, 2,...,n. Show that the following procedure, which simply drops all the superscripts, is correct, and thus ...Suppose that we order the edge relaxations in each pass of the Bellman-Ford algorithm as follows. Before the first pass, we assign an arbitrary linear order v1, v2,..., v |v| to the vertices of the input graph G = (V, E). ...Let f be a flow in a network, and let α be a real number. The scalar flow product, denoted α f, is a function from V × V to R defined by (αf)(u, v) = α • f (u, v). Prove that the flows in a network ...A path cover of a directed graph G = (V, E) is a set P of vertex-disjoint paths such that every vertex in V is included in exactly one path in P. Paths may start and end anywhere, and they may be of any length, including 0. ...Post your question

0