4. Dijkstra’s Algorithm (20 pts;6+6+4+4) Dijkstra’s single source shortest paths

Question

4. Dijkstra’s Algorithm (20 pts;6+6+4+4) Dijkstra’s single source shortest paths algorithm finds shortest paths from a (source) vertex to all other vertices. Once the algorithm is executed on a source, say x, the distances to all vertices from this source can be stored in a file. Subsequently, to determine the shortest distance from x to any vertex, the algorithm need not be executed again; instead, the distance is simply read off the file. Consider an application that works on a directed graph that has 1,024 vertices and 10,240 edges, and positive edge weights. (Remember, log2(1, 024) = 10)

• In any single run, the application gets the shortest distance from x to y in the graph, where x and y are input vertex numbers.

• It maintains a single file into which it can dump shortest distances from any vertex (so at any time this file can contain sets of shortest distances from numerous vertices)

• It takes exactly (n+e)*log(n) time to execute Dijkstra’s algorithm for a given source vertex (This is not a big-oh order; it is an exact number.)

• It takes exactly 100*log(n) time to find whether the shortest distance from x to y is in the distance file, and if so, the actual distance. Let’s call this process “file lookup”.

• It takes exactly 100*log(n) time to store in the file the shortest distances from any source x - call this process “file store”.

a) What would your strategy be to determine the shortest distance from x to y, for any single run of the application with x and y as parameters? Write your strategy in the form of an algorithm, i.e. a sequence of steps. Do not write any Java code. I HAVE THIS ANSWER. PLEASE DO C AND D. This is the answer for part a:

For a given (x,y) pair:

Step 1: Check if file is empty. If empty, goto Step 2 else goto Step 4.

Step 2: For each distinct source vertex 'x', run Dijkastra algorithm to calculate shortest distance to every other reachable vertex 'y' and store the entries in file (format: x y distance). Goto Step 3.

Step 3: Sort the entries in file with respect to a given source vertex in ascenting order of shortest distances of this vertex to other vertices. This will form groups of shortest distance with respect to a given vertex. For sorting, quicksort can be used. An index can be prepared to store the no. of shortest distances against a given source vertex 'x'. This will help in locating the group of 'x' during look-up.

Step 4: Locate the group of source vertex 'x' in index as described in Step 3. Once the group is located, perform search in the group to locate the shortest distance for the destination vertex 'y'. For searching, binary search can be used. Goto Step 5.

c) If, instead of 100*log(n), it took k*log(n) time for file lookup of distance, how would your strategy of (a) depend on the value of k, for a graph with 1,024 vertices and 10,240 edges? Explain.

d) If we fixed the file lookup time at 100*log(n), then how would your strategy of (a) depend on general values of n and e? Explain.

Explanation / Answer

c) The time taken to read from the file is k*log(n) in this case it is k*log(1024) but we have another option, instead we can run the algorithm again. The time to run is (1024+10240)*log(1024) vs k*log(1024). So the choice comes down to whether k > 11264 if that is that we will have only step where we run the algorithm and return the value, or if k < 11264 then we will stick with the present setup.

d) Even here it comes down to (n+e)*log(n) vs 100*log(n). So this is (n+e) vs 100. So even here if (n+e)<100, we will have only one step where we run the algorithm and return the value. Otherwise we stick to the original setup.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

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