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 (MR : 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 mij = 0
then mij = Infinity
W: = MR
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 mij = 0
then mij = Infinity
W: = In
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. wij:= min(wij, wik + wkj)wij:= min(wij, wik + wkj)
F. wij:= max(wij, wik + wkj)wij:= max(wij, wik + wkj)
G. return W{W = [wij] is MR*}
Get Answers For Free
Most questions answered within 1 hours.