Look up the following graph algorithms and answer the questions below: The Floyd
ID: 3828836 • Letter: L
Question
Look up the following graph algorithms and answer the questions below:
The Floyd-Warshall algorithm for the All-Pairs Shortest Path problem.
1. What problem is the algorithm is trying to solve? What does it mean to solve the problem/What is the output of the algorithm? Is this output the best solution, or an approximation?
2. Why does the algorithm work? How? Be specific; you shouldn't give pseudocode, but you might write (for example) "loop through each node and add up the weights of all incoming and outgoing edges".
3. What is the run time complexity of this algorithm? Justify your answer using the algorithm description you gave above.
Explanation / Answer
1. When we are given a directed graph with weights assigned to the edges, we can find the shortest distance between every pair of vertices using Floyd-Warshall Algorithm.
The output of the algorithm is a matrix (or 2D array) which holds the shortest distance between row and column vertex.
This is the best solution which means that it does find the shortest possible paths for real as long as there is no negative cycle.
------------
2. The algorithm works by picking up each vertex one by one as the intermediate vertex such that all the shortest paths which include that vertex are updated.
Basically it has two steps:
FOR EACH VERTEX 'k' :
-----------
3. To analyze the time complexity of this algorithm look at the steps in part 2.
We are looping over each vertex while considering it as intermediate node. And for each of those intermediate vertices, we are checking the shortest path between every pair of node.
To check every pair of node, we need 2 levels of nested loops, so in total we have 3 levels of nested loops iterating over the number of vertices.
If number of vertices is n. Then time complexity must be O(n3).
If you have any queries ask in the comments.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.