Design and analysis algorithms

1. Suppose you have an undirected graph with only positive integer edge weights. How can you use BFS to find the length of the shortest path from a source vertex to every other vertex in O((E+V)*D) time, where D is the maximum weight on an edge. Split an edge (u,v) with weight W > 1 into W edges, each with weight 1 and run BFS. 2. Consider a directed weighted graph with non-negative edge weights. For some cases, it is necessary to compute the length of the shortest path from every vertex v to a target vertex t. Describe how you can compute this in the same time complexity as in Dijkstra's algorithm. Reverse edges and solve for single source shortest path from t. Reverse edges in the path. 3. Consider a directed graph where each edge has some existence probability, i.e., say an edge e exists with probability Pr(e), where 0 <= Pr(e) <= 1. If a path from u to v has the edges e_1, e_2, ..., e_k, then the probability that the path exists is given by Pr(e_1) x Pr(e_2) x ... x Pr(e_k). Given a source vertex s and a target vertex t, describe how you can use Dijkstra's algorithm to find a path from s to t that has the maximum probability of existing. Take – log Pr(e) for each edge, and solve for shortest path from s to t. 4. Given a directed acyclic graph, find the length of the longest path in the graph in O(n+m) time. Note that we are NOT looking for the longest path starting at a particular vertex, rather the overall longest path that can start at any arbitrary vertex If graph has only negative edges, output the edge with maximum value. Otherwise, perform a topological sort, and say output order is v_1, v_2, …, v_n. Let dist(v_i) = 0 and parent(v_i) = null for all vertices v_i. for i = 1, 2, …, n for all adjacent vertices v_j of v_i if dist(v_j) < dist(v_i) + w(v_i,v_j) dist(v_j) = dist(v_i) + w(v_i,v_j) parent(v_j) = v_i Find vertex with max dist() value, and use parent() to construct path