You are given a directed, weighted graph G = (V, E, w), in which the edge-weight

Question

You are given a directed, weighted graph G = (V, E, w), in which the edge-weights are integers bounded in absolute value by some fixed polynomial in n (the number of vertices). The graph is given in adjacency list format-specifically, for each vertex you are given a list of its out-neighbors and the corresponding edge weights. However the graph is given on a read-only memory medium. At your disposal you have another memory, which is read-write, but can hold only O(log^2 n) bits. Show how you can, given vertices s, t belongsto V, compute the length of a shortest s path or else determine that the graph has a negative-weight cycle.

Explanation / Answer

For the correctness of Dijkstra, it is sufficient to show that d[v] =
(s, v) for every v V when v is added to s. Given the shortest s v path and given
that vertex u precedes v on that path, we need to verify that u is in S. If u = s, then
certainly u is in S. For all other vertices, we have defined v to be the vertex not in S
that is closest to s. Since d[v] = d[u] + w(u, v) and w(u, v) > 0 for all edges except
possibly those leaving the source, u must be in S since it is closer to s than v.
It was not sufficient to state that this works because there are no negative weight cycles.
Negative weight edges in DAGs can break Dijkstra’s in general, so more justification
was needed on why in this case Dijkstra’s works

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.