Question

Identify the steps of an algorithm that uses the concept of interior vertices in a path to find the length of the shortest path between two vertices in a directed graph, if such a path exists. (Check all that apply.)

A. procedure Warshall (M_R : n × n zero–one matrix)procedure Warshall (MR : n × n zero–one matrix)

B. for i : = 1 to n
for j : = 1 to n
if m_ij = 0 then m_ij = Infinity
W: = M_R

for i : = 1 to n for j : = 1 to n if mij = 0 then mij = Infinity W: = MR

C. for i : = 1 to n
for j : = 1 to n
if m_ij = 0 then m_ij = Infinity
W: = I_n

for i : = 1 to n for j : = 1 to n if mij = 0 then mij = Infinity W: = In

D. for k : = 1 to n
for i : = 1 to n
for j : = 1 to nfor k : = 1 to n for i : = 1 to n for j : = 1 to n

E. w_ij:= min(w_ij, w_ik + w_kj)wij:= min(wij, wik + wkj)

F. w_ij:= max(w_ij, w_ik + w_kj)wij:= max(wij, wik + wkj)

G. return W{W = [w_ij] is M_R*}

Answer 1

The objective is to devise an algorithm with the use of the concept of interior vertices in a path to nd the length of the shortest path between two vertices in a directed graph, if such a path exists.

The required algorithm is; Step 1: Procedure Warshall M nxn zero-one matrix) W Mr (where each zero is replaced by o) Step 2: For k: to n For i:1 to For j:1 to Step 3: Step 4: return WW [w,s M Thus, the above algorithm Ond the length of the shortest path between two vertices in a directed graph, if such a path exists.