Floyd's algorithm

Question 1

What does Floyd’s algorithm do?

Answer 1

FA calculates the length of the shortest path between all pairs of nodes in a graph.

Question 2

Describe Floyd’s algorithm in pseudocode. Be very careful to get the for loop constants to match up with the matrix accesses.

Answer 2

With adjM as the adjacency matrix:

for (int k = 1; k < n; k++) {
\_\_ for (int i = 1; i < n; i++) {
\_\_\_\_ for (int j = 1; j < n; j++) {
\_\_\_\_\_\_ int ik = adjM(i,k)
\_\_\_\_\_\_ int kj = adjM(k,j)
\_\_\_\_\_\_ int ij = adjM(i,j)
\_\_\_\_\_\_ if (ik + kj < ij) {
\_\_\_\_\_\_\_\_ adjM(i,j) = ik + kj;
\_\_\_\_\_\_ }
\_\_\_\_ }
\_\_ }
}

Question 3

Describe a mnemonic for getting the order of the variables right.

Answer 3

KIJ

Killing is joke.

Question 4

Describe a rule for getting the matrix accesses right.

Answer 4

A(i,k) + A(k,j)

Getting for i to j requires you to start at i and end up at j. k is the intermediate node we use for that.

k is our current neighborhood and we want to bridge its neighbors.