Floyd's algorithm

Floyd's algorithm

Spec 2.2 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Floyd's algorithm finds the shortest distance between every pair of vertices.
  • It uses a distance table and a route table, each with a row and column per vertex.
  • Iteration kk uses the kkth vertex as the pivot and tests every other pair.
  • Update only if d(X,K)+d(K,Y)<d(X,Y)d(X,K)+d(K,Y)<d(X,Y), and copy the route entry from (X,K)(X,K).
  • A network with nn vertices needs exactly nn iterations.

What Floyd's algorithm does

The distance table holds the shortest known distances and the route table holds the first vertex to travel to.

The distance table has 0 on the leading diagonal. Each other entry is the direct road length, or ∞\infty if there is none.

The route table entry in row XX, column YY is the first vertex to go to when travelling from XX to YY. At the start each entry is the column vertex YY.

For an undirected network the distance table is symmetric. For a directed network it need not be.

Distance table

  • Diagonal is 0
  • Direct length, or ∞\infty
  • Updated with shorter totals

Route table

  • Entry is a first vertex
  • Starts as the column vertex
  • Copied from (X,K)(X,K)

In the initial route table, what is the entry in row BB, column DD?

One iteration

Take the next vertex as pivot KK and, for every other pair, check whether going through KK is strictly shorter.

Iteration kk uses the kkth row and column. For every pair XX, YY (neither being the pivot KK), compare with going through KK:

d(X,K)+d(K,Y)<d(X,Y)d(X,K)+d(K,Y)<d(X,Y)

If true, replace d(X,Y)d(X,Y) by the sum and set route entry (X,Y)(X,Y) equal to route entry (X,K)(X,K). Otherwise change nothing.

The pivot's own row and column never change in its iteration. Treat ∞\infty as larger than any number.

  1. 1

    Pick the pivot

    the kth vertex for iteration k

  2. 2

    Test each pair

    is d(X,K) + d(K,Y) less than d(X,Y)?

  3. 3

    Update

    new distance, route entry copied from (X,K)

  4. 4

    Otherwise

    leave both tables unchanged

One iteration with pivot K

For a pair XX, YY and pivot KK: d(X,K)=3d(X,K)=3, d(K,Y)=4d(K,Y)=4 and d(X,Y)=7d(X,Y)=7. What do you do?

A worked example

Each iteration tests one pivot; after all four the distance table gives every shortest distance.

Roads AB=2AB=2, AC=3AC=3, BC=7BC=7, BD=10BD=10, CD=4CD=4. Find all the shortest distances.

Update both d(X,Y)d(X,Y) and d(Y,X)d(Y,X) for an undirected network. Show each iteration with its changed entries to earn method marks.

AB 2AC 3BC 7BD 10CD 4ABCD
The network for the worked example.

Worked example

Apply Floyd's algorithm to the network.

In the worked example, why does A→DA\to D change from 12 to 7 in the pivot CC iteration?

Reading the route

Look up (X,Y)(X,Y) for the next vertex, then repeat from there until you reach YY. Check the lengths add to the table entry.

The distance table gives the length. To find the route from XX to YY, look up (X,Y)(X,Y) in the route table to get the next vertex ZZ. Then look up (Z,Y)(Z,Y) and continue until you reach YY.

From the worked example, B→DB\to D: (B,D)=A(B,D)=A, (A,D)=C(A,D)=C, (C,D)=D(C,D)=D. The route is B−A−C−DB-A-C-D with length 2+3+4=92+3+4=9.

  1. 1

    (B,D) = A

    first move: B to A

  2. 2

    (A,D) = C

    next: A to C

  3. 3

    (C,D) = D

    last: C to D

Route from B to D

The route table has (P,S)=Q(P,S)=Q and (Q,S)=S(Q,S)=S. What is the route from PP to SS?

Floyd's or Dijkstra's

Floyd's gives every pair at once; Dijkstra's is quicker when only one start vertex is needed.

One run of Floyd's algorithm gives the shortest distance between every pair. Dijkstra's gives them only from one start vertex, so it would be run from each vertex in turn.

A network with nn vertices needs exactly nn iterations on an n×nn\times n table.

For a directed network treat d(X,Y)d(X,Y) and d(Y,X)d(Y,X) separately and only use arcs that exist.

Floyd's

Finds:
Every pair
Method:
nn iterations

Dijkstra's

Finds:
One start vertex
Method:
Labelling

How many iterations does Floyd's algorithm need for a network with 6 vertices?

Try an exam question

A network has roads PQ=4PQ=4, QR=3QR=3 and PR=9PR=9. Apply Floyd's algorithm, with PP, QQ, RR as pivots in that order, to find the shortest distance from PP to RR and its route.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

After iteration 1 (pivot AA), what is the entry in row BB, column CC of the distance table?

1 mark, marked against the mark scheme

Revision notes