The link below gives a version of the Floyd-Warshall algorithm that uses a 3-dim

Question

The link below gives a version of the Floyd-Warshall algorithm that uses a 3-dimensional array.

http://www.jennylam.cc/courses/146-s17/dp1.pdf

Notice that the values dist[-] [-] [k] in the table only ever depend on values of the form dist [-] [-] [k-1], and not on any smaller values of the 3rd index.

(a) Using this observation, propose a minor modification to this algorithm which uses two 2-dimensional arrays instead. Give your answer in code or pseudocode.

(b) How are the time and space complexities affected by this modification? If there is a changem what is the new complexity ?

Explanation / Answer

output:

Time Complexity: O(V^3)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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