Exercise 8 Theory: Floyd Warshall NB! Consult the norwegian exercise-page for pictures Exercise 1: -------------------------------- Apply Warshall's algorithm on this graph (insert graph here) The matrix R^(k) shows whether there exists a path from node i to node j only passing through nodes up to or equal k (or no nodes at all). (Note that a=1, b=2, and so on). Note: this is not Floyd-Warshall's algoritm but Warshall's algorithm. In the book this algorithm is known as Transitive-Closure and can be found on page 633 (2nd ed.) There is still a difference between Transitive-Closure and Warshall's algorithm as it is not intended to have one on the diagonal unless there exists self loops. The code "i=j or" has to be removed from line 4 in Transitive-Closure in order to give the correct answer. a) How does R^(2) look? b) How does R^(5) look? c) Can Warshall's algorithm be used to determine if a directed graph is acyclic? Yes No d) Can Transitive-Closure be used to determine if a directed graph is acyclic? - Yes - No Exercise 2: -------------------------------- Here Floyd Warshall is used as it is described in Cromen. D^k is the distance matrix after k-th iteration. We're looking at the same graph as in exercise 1. a) Fill in d12 and d35 in D^1 (as shown below, D^0 = W) (insert graph here) - d12 = 2, d35 = 3 - d12 = 2, d35 = 5 - d12 = INF, d35 = INF - d12 = 3, d35 = INF - d12 = 3, d35 = 3 - Impossible to determine b) Fill in d14, d23 and d53 in D^5 (as shown below, D^0 = W) - d14 = 12, d23 = 1, d53 = 4 - d14 = 8, d23 = 3, d53 = INF - d14 = 8, d23 = 2, d53 = INF - d14 = 12, d23 = 3, d53 = INF - d14 = INF, d23 = 1, d53 = 2 - d14 = 12, d23 = 1, d53 = 4 - Impossible to determine c) How much extra storage space does the implementation in the book use? - Theta(1) - Theta(n) - Theta(n^2) - Theta(n^3) Exercise 3: -------------------------------- Below there are given different graphs (see the exercise-page). What's the theoretically fastest algorithm (best O) for the "shortest path, one-to-all"-problem, and how fast is the algorithm for this graphs? (NB: We assume the Extract-Min-Operation takes O(V) time in Dijkstra's algorithm) a) (See graph at exercise-page) or http://www.idi.ntnu.no/~algdat/arkiv/ovingsfiler/FW-oppg3a.png - Bellmann-Ford - Dag-Shortest-Path - Floyd-Warshall - Dijkstra's algoritm - None of the above algorithms can solve the problem - None of the is uniqely best b) Asymptotically tightest running time of the fastest algorithm(s) in exercise a) is...? - O(1) - O(E + V) - O(VlgE) - O(ElgV) - O(E + VlgV) - O(V + ElgE) - O(EV) - O(E^2) - O(V^2) - O(E^3) - O(V^3) - None of the algorithms could solve the problem c) (See graph at exercise-page) or http://www.idi.ntnu.no/~algdat/arkiv/ovingsfiler/FW-oppg3c.png - Bellmann-Ford - Dag-Shortest-Path - Floyd-Warshall - Dijkstra's algoritm - None of the above algorithms can solve the problem - None of the is uniqely best d) Asymptotically tightest running time of the fastest algorithm(s) in exercise c) is...? - O(1) - O(E + V) - O(VlgE) - O(ElgV) - O(E + VlgV) - O(V + ElgE) - O(EV) - O(E^2) - O(V^2) - O(E^3) - O(V^3) - None of the algorithms could solve the problem e) (See graph at exercise-page) or http://www.idi.ntnu.no/~algdat/arkiv/ovingsfiler/FW-oppg3e.png - Bellmann-Ford - Dag-Shortest-Path - Floyd-Warshall - Dijkstra's algoritm - None of the above algorithms can solve the problem - None of the is uniqely best f) Asymptotically tightest running time of the fastest algorithm(s) in exercise e) is...? - O(1) - O(E + V) - O(VlgE) - O(ElgV) - O(E + VlgV) - O(V + ElgE) - O(EV) - O(E^2) - O(V^2) - O(E^3) - O(V^3) - None of the algorithms could solve the problem g) (See graph at exercise-page) or http://www.idi.ntnu.no/~algdat/arkiv/ovingsfiler/FW-oppg3g.png - Bellmann-Ford - Dag-Shortest-Path - Floyd-Warshall - Dijkstra's algoritm - None of the above algorithms can solve the problem - None of the is uniqely best h) Asymptotically tightest running time of the fastest algorithm(s) in exercise g) is...? - O(1) - O(E + V) - O(VlgV) - O(ElgV) - O(E + VlgV) - O(V + ElgE) - O(EV) - O(E^2) - O(V^2) - O(E^3) - O(V^3) - None of the algorithms could solve the problem i) (See graph at exercise-page) or http://www.idi.ntnu.no/~algdat/arkiv/ovingsfiler/FW-oppg3i.png - Bellmann-Ford - Dag-Shortest-Path - Floyd-Warshall - Dijkstra's algoritm - None of the above algorithms can solve the problem - None of the is uniqely best j) Asymptotically tightest running time of the fastest algorithm(s) in exercise i) is...? - O(1) - O(E + V) - O(VlgV) - O(ElgV) - O(E + VlgV) - O(V + ElgE) - O(EV) - O(E^2) - O(V^2) - O(E^3) - O(V^3) - None of the algorithms could solve the problem Excersise 4: -------------------------------- Below there are given different graphs (see the exercise-page). What's the theoretically fastest algorithm (best O) for the "shortest path, *all-to-all*"-problem, and how fast is the algorithm for this graphs? (NB: We assume the Extract-Min-Operation takes O(V) time in Dijkstra's algorithm) a) (See graph at exercise-page) or http://www.idi.ntnu.no/~algdat/arkiv/ovingsfiler/FW-oppg3a.png - Dijkstra's algoritm, runned V times - Dag-Shortest-Path, runned V times - Floyd-Warshall - Bellmann-Ford, runned V times - None of the above algorithms can solve the problem (without modifications) - None of the is uniqely best b) Asymptotically tightest running time of the fastest algorithm(s) in exercise a) is...? - O(1) - O(EV + V^2) - O(VlgE) - O(VlgV) - O(V^2 + VElgE) - O(VE + V^2 + lgV) - O(EV^2) - O(VE^2) - O(V^2) - O(E^3) - O(V^3) - None of the algorithms could solve the problem c) (See graph at exercise-page) or http://www.idi.ntnu.no/~algdat/arkiv/ovingsfiler/FW-oppg3c.png - Dijkstra's algoritm, runned V times - Dag-Shortest-Path, runned V times - Floyd-Warshall - Bellmann-Ford, runned V times - None of the above algorithms can solve the problem (without modifications) - None of the is uniqely best d) Asymptotically tightest running time of the fastest algorithm(s) in exercise c) is...? - O(1) - O(EV + V^2) - O(VlgE) - O(VlgV) - O(V^2 + VElgE) - O(VE + V^2 + lgV) - O(EV^2) - O(VE^2) - O(V^2) - O(E^3) - O(V^3) - None of the algorithms could solve the problem e) (See graph at exercise-page) or http://www.idi.ntnu.no/~algdat/arkiv/ovingsfiler/FW-oppg3e.png - Dijkstra's algoritm, runned V times - Dag-Shortest-Path, runned V times - Floyd-Warshall - Bellmann-Ford, runned V times - None of the above algorithms can solve the problem (without modifications) - None of the is uniqely best f) Asymptotically tightest running time of the fastest algorithm(s) in exercise e) is...? - O(1) - O(EV + V^2) - O(VlgE) - O(VlgV) - O(V^2 + VElgE) - O(VE + V^2 + lgV) - O(EV^2) - O(VE^2) - O(V^2) - O(E^3) - O(V^3) - None of the algorithms could solve the problem g) (See graph at exercise-page) or http://www.idi.ntnu.no/~algdat/arkiv/ovingsfiler/FW-oppg3g.png - Dijkstra's algoritm, runned V times - Dag-Shortest-Path, runned V times - Floyd-Warshall - Bellmann-Ford, runned V times - None of the above algorithms can solve the problem (without modifications) - None of the is uniqely best h) Asymptotically tightest running time of the fastest algorithm(s) in exercise g) is...? - O(1) - O(EV + V^2) - O(VlgE) - O(VlgV) - O(V^2 + VElgE) - O(VE + V^2 + lgV) - O(EV^2) - O(VE^2) - O(V^2) - O(E^3) - O(V^3) - None of the algorithms could solve the problem i) (See graph at exercise-page) or http://www.idi.ntnu.no/~algdat/arkiv/ovingsfiler/FW-oppg3i.png - Dijkstra's algoritm, runned V times - Dag-Shortest-Path, runned V times - Floyd-Warshall - Bellmann-Ford, runned V times - None of the above algorithms can solve the problem (without modifications) - None of the is uniqely best j) Asymptotically tightest running time of the fastest algorithm(s) in exercise i) is...? - O(1) - O(EV + V^2) - O(VlgE) - O(VlgV) - O(V^2 + VElgE) - O(VE + V^2 + lgV) - O(EV^2) - O(VE^2) - O(V^2) - O(E^3) - O(V^3) - None of the algorithms could solve the problem