Question

Q1: Here we consider finding the length of the shortest path between all pairs of nodes in an undirected, weighted graph G. For simplicity, assume that the n nodes are labeled 1; 2; : : : ; n, that the weight wij of any edge e = (i; j) is positive and that there is an edge between every pair of nodes. In this question, the goal is to solve this via dynamic programming. Note that the algorithm you will develop is not the Bellman-Ford algorithm.

1.1: Let D[i; j; k] be the length of the shortest path from node i to node j in which the intermediate nodes on the path are all in the set f1; 2; : : : ; kg. Note that D[i; i; k] = 0 for all i and

k and that D[i; j; 0] = w_ij for all i 6= j. A formula for D[i; j; k] with two missing arguments is:

D[i; j; k] = min(D[i; j; k - 1];D[i; k; k - 1] + D[k; j; k - 1]

when k >= 0. Fill in the two missing arguments.

1.2: Write pseudo-code for an efficient dynamic programming (using the above formula) to compute the shortest path between every pair of nodes. Hint: You need to specify how each D[i; j; k] is computed, the order in which they are computed, and the final output.

1.3: What is the running time of your algorithm? Justify your answer?

1.4: What is the number of edge-disjoint paths between node 1 and node 2 in G? Your answer should be a function of n. Recall that G had an undirected edge between every pair of nodes.

Answer 1

Question 1) D[i; j; k] = min(D[i; j; k - 1]; D[i; k; k - 1] + D[k; j; k - 1]; D[i; j; k]; Wij)

Question 2)

main:

for k = [1; n]

for i = [1; n]

for j = [1; n]

D[i,j,k] = INF

for k = [1; n]

for i = [1; n]

for j = [1; n]

D[i, j, k] = min(D[i,j,k], D[i,j,k-1],D[i,k,k-1]+D[k,j,k-1],W[i,j])

Question 3)

This algorithm needs to fill N*N*N table. Each entry is calculated once and each calculation can be done in O(1). So time complexity for this algorithm is O(N^3)

Question 4)

f(N) = N-1
Let's say starting node is X and ending node is Y. Each of them have N-1 different edges connected to them so answer can be at most N-1, we can not get N or more paths. Now let's prove that N-1 different paths exists. Let's say that Z is node in N different from X and Y, there are N-2 such nodes. As there is edge between any two nodes we now that X is connected to Z and Z is connected to Y, so we have path X-Z-Y. As Z has N-2 different values we have N-2 different paths which have different edges in them. Also X is connected with Y and X-Y path exists and in total we Have N-1 paths.


Comment down for any queries
please give a thumbs up