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