Exercise 7 a) If I, in a graph G, have found a shortest path from node A to node F, do I also have a shortest path from node F to node A? Yes, it doesn't matter if G is directed or undirected If G is directed If G is undirected No b) I have, in a graph G, found a shortest path from node A to node F via node D. Have I also found a shortest path from A to D, and D to F? Yes, it doesn't matter if G is directed or undirected If G is directed If G is undirected No c) I have, in a graph G, found a shortest path from node A to node D, and from node D to node F. Have I also found a shortest path from A to F? If G is directed If G is undirected Yes, it doesn't matter if G is directed or undirected No d) If all edges in a graph has weight = 5, it is most efficient to use which algorithm to find a shortest path? BFS DAG shortest path Dijkstra Bellman-Ford Floyd-Warshall All of them are equally efficient None of them has an advantage e) If all edges in a strongly-connected graph has the weight = -5, it most efficient to use what algorithm to find a shortest path? BFS DAG shortest path Dijkstra Bellman-Ford Floyd-Warshall All of them are equally efficient None of them has an advantage Exercise 2 a) We are going to find the shortest path from one node to all other nodes in an acyclic graph without negative edges, and we know that |E| = O(V^2/log V). What algorithm should we use? Dijkstra with heap Difkstra with linear array Bellman-Ford Dag-Shortest-Path b) We are going to find the shortest path from one node to all other nodes in a graph without negative edges, and we know that |E| = w(V^2/log V) (where w is little omega). What algorithm should we use? Dijkstra with heap Difkstra with linear array Bellman-Ford Floyd-Warshall c) We are going to find the shortest path from all nodes to all other nodes in a graph without negative edges, and we know that |E| = o(V^2/log V) (where o is little o). What algorithm should we use? Dijkstra with heap, from every node in the graph Difkstra with linear array, from every node in the graph Bellman-Ford from every node in the graph Floyd-Warshall d) We are going to find the shortest path from all nodes to all other nodes in a graph without negative edges, and we know that |E| = w(V^2) (where w is little omega). What algorithm should we use? Dijkstra with heap, from every node in the graph Difkstra with Fibonacci heap, from every node in the graph Bellman-Ford from every node in the graph Floyd-Warshall Exercise 3 It can be a bit constraining that Dijkstra's algortihm doesn't work on graphs with negative edges. Here are som suggestions for solving this problem in certain cases. a) We can locate the least edge-weight, and add a constant to all weights such that this smallest becomes equal to 1. This will work in all cases. this will work in some cases, but not in general This will work if the constant is lower than the largest weight This will work if the constant is lower than the least positive edge-weight This will never work b) If the graph only containts negative edges, we can just take the abslolute value of all edge-weights, and then choose nodes with the longest path instead of the shortest. This will work in all cases. This will work in some cases, but not in general This will work if there was no negative cycles in the original graph This will never work c) We can replace edge-weight w with the new weight 2^w This will work in all cases this will work in some cases, but not in general This will work if there was no negative cycles in the original graph This will never work Exercise 4: The figure above shows a directed graph with weights on the edges. a) Use an algorithm on the graph and find the shortest distance from A to all other nodes, the the final distances will then be?(A is index number 0, B number 1, and so on) - [0,8,6,1,5,3,3] - [0,11,9,1,9,3,5] - [0,8,6,1,5,2,3] - [0,11,9,1,5,2,3] b) In which order are the nodes chosen if one uses Dijkstra? - A, D, G, F, E, C, B - A, D, G, E, F, C, B - A, D, G, E, C, F, B - A, D, F, G, E, C, B The figure above shows a directed graph with weights on the edges. c) Use an algorithm, Dijkstra or Bellman-Ford, as described in Cormen, on the graph and find the shortest distance from A to all other nodes. The final distances will then be? (A is index number 0, B number 1, and so on) - [0,-1,6,1,5,2,3] - [0,-4,6,1,5,2,3] - [0,-1,6,1,5,2,3], but you have to use Bellman-Ford - [0,-4,6,1,5,2,3], but you have to use Bellman-Ford - You can not find the shortes path because the graph contains negative cycles The figure above shows a directed graph with weights on the edges d) Use an algorithm, Dijkstra or Bellman-Ford, as described in Cormen, on the graph and find the shortest distance from A to all other nodes. The final distances will then be? (A is index number 0, B number 1, and so on) - [0,2,0,-1,-1,-3,-1] - [0,0,-2,-1,-3,-3,-1] - [0,2,0,-1,-1,-3,-1], but you have to use Bellman-Ford - [0,0,-2,-1,-3,-3,-1], but you have to use Bellman-Ford - You can not find the shortes path because the graph contains negative cycles Exercise 5: a) What happens if one changes line 4 in Dijkstra's algorithm: while Q != Ø with: while |Q| > 1 (That is, the loop is run as long as the queue has more than one element)? - Dijkstra's will never give the correct answer, because Relax no longer is run on the final node and one cannot be sure that the solution is correct! - Dijkstra's will give the correct answer, because the final element in the queue cannot possibly improve the current solution - Dijkstra's will not give the correct answer, because there will always be a node in the graph, where the shortest path from the source to this node goes via the last element b) What does 'Dijkstras(G,w,s)'(Dijkstra's algorithm) do if one changes the min-priority queue to a max-priority queue (and thus changes the Extract-Min call with Extract-Max) and change the Relax-subroutine to the following: Relax(u,v,w): 1. if v.d < u.d + w(u,v) 2. then v.d = u.d + w(u,v) 3. v.pi = u - Finds the shortest paths from one start node to all other nodes - Finds the longest paths from one start node to all other nodes - Finds the paths from one node to all others, in which the edge with maximal weight is minimal - Finds the shortest paths from all nodes to all other nodes - Finds the paths from one node to all others, in which ones visists the fewest possible nodes - This is an attempt on doing one of the above, however, it will not work Relax subroutine for c): 1. if v.d > w(u,v) 2. then v.d = w(u,v) 3. v.π = u c) Suppose we now consider dijkstra on a undirected connected graph. What does 'Dijkstras(G,w,s)'(Dijkstra's algorithm) do if one changes the Relax subroutine as above and add a line 9 to Dijkstra which sets u.d = - inf after all nodes from u are relaxed. - It finds a minimum spanning tree - It finds the shortest path from one start node to all other nodes, where the maximal edge is minimal - It finds the shortest path from one start node to all other nodes, where the number of edges are minimal - It finds the shortest path from one start node to all other nodes, but none of the above statements are correct - It is an attempt on one of the above, but it will not work d) Suppose we have a graph in which the weights of the edges are positive integers, and let E be the number of edges and V the number of nodes. What does 'Dijkstras(G,w,s)'(Dijkstra's algorithm) do if one changes all weights of all edges by the formula w'(u,v) = (E + Floor(V lg V))*w(u,v) + 1? - It finds the shortest path from one start node to all other nodes, where the maximal edge is minimal - It finds the shortest path from one start node to all other nodes, where the number of edges are minimal - It finds the shortest path from one start node to all other nodes, but none of the above statements are correct - It finds a minimum spanning tree - It is an attempt on one of the above, but will not work