Prove that the current matrix (i.e., D_k) in the sequence of Floyd\'s Algorithm

Question

Prove that the current matrix (i.e., D_k) in the sequence of Floyd's Algorithm can be written over its predecessor (i.e., D_k-1).

6. a. Prove that a nonempty dag must have at least one source.

b. How would you find a source (or determine that such a vertex does not

exist) in a digraph represented by its adjacency matrix? What is the time

efficiency of this operation?

c. How would you find a source (or determine that such a vertex does not

exist) in a digraph represented by its adjacency lists? What is the time

efficiency of this operation?

Explanation / Answer

1)

On the k-th iteration, the Floyd's algorithm determines shortest paths between every pair of vertices i, j that use only vertices among 1,%u2026,k as intermediate

D(k)[i,j] = min {D(k-1)[i,j], D(k-1)[i,k] + D(k-1)[k,j]}

6.

a) Suppose G is a DAG without any sources.

Start from any vertex u in G , and follow some edge (v , u)

backwards to v

Again follow some edge backwards from v , and repeat this

forever

If G has n vertices, then after n + 1 steps, we would have

visited some vertex a second time. Thus, we have found a

cycle which gives us a contradiction

b) For each vertex v, check if there is any incoming vertex or not. If not then v is a source. It will take O(n^2) time.

c) For each vertex v, check the size of each adjacency list of v. If it is 0 then v is a source. It will take O(n) time.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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