D1 2.2 - Floyd's algorithm | Edexcel A-Level Further Mathematics

You will construct directed distance and route tables, perform Floyd's iterations in the specified order, and read complete shortest routes from the final next-hop table.

All pairs of nodes, not one starting node

An initial table says the distance from $D$ to $C$ is $\infty$ , but the completed table says $13$ . Has the algorithm invented a road? No: it has found an indirect route through roads already present.

You already know

Dijkstra gives shortest distances from one specified start. A directed arc can be travelled only in its arrow direction. A route's length is the sum of its arc weights.

Floyd finds shortest distances between every ordered pair of nodes in one sequence of tables. Four nodes give twelve ordered pairs with different endpoints. A route from $A$ to $B$ need not have the same distance as a route from $B$ to $A$ .

[DIAGRAM: asset_name: A directed network for Floyd's algorithm; asset_slug: 9fm0-d1-168-directed-network; caption: All six arcs are directed; use the arrow direction when constructing the initial table.; description: Four nodes A, B, C and D with directed arcs A to B weight4, A to C weight12, B to C weight3, B to D weight10, C to D weight2 and D to A weight6; the diagonal crossing has no node.]

Distance table and route table

In a distance table, row $i$ , column $j$ gives the current best distance from $i$ to $j$ . In the corresponding next-hop route table, that entry gives the first node to go to after leaving $i$ on the recorded route to $j$ .

The initial distance table records direct arcs only. An $\infty$ entry means no direct arc is available in that direction; later iterations may replace it by a finite indirect distance. If it remains $\infty$ in the final table, the destination cannot be reached from that start.

Key idea

Read rows as origins and columns as destinations. Floyd's distance table records lengths; its route table records next nodes, not distances or complete routes.

Separate “no direct arc” from “no route at all”.

Constructing the initial tables

Use the stated node order for both rows and columns. Copy each directed arc into its own row-to-column position; do not automatically put the same weight in the reverse position.

Initial table conventions

The initial distance entry is the direct arc weight, or $\infty$ if there is no direct arc. Use a dash on the diagonal, interpreted as distance $0$ in calculations.

In Pearson's initial route table, each row is the list of column names: $A,B,C,D$ here. An entry corresponding to an infinite distance is a placeholder, not evidence that a route exists.

With a finite direct arc, the first node after leaving the origin is simply its destination. That explains the repeated column names in the route table. The unused diagonal route entries can retain their own node names.

Not in the formula booklet: learn it.

Worked example 1: direction matters

Question. Construct the initial distance and route tables, in order $A,B,C,D$ , for

A\to B:4,\quad A\to C:12,\quad B\to C:3,\quad B\to D:10,\quad C\to D:2,\quad D\to A:6

Plan. Enter only the six direct arcs, fill missing directed connections with $\infty$ , then write the initial next-hop table.

The distance table is

\mathbf D^{(0)}= \begin{array}{c|rrrr} &A&B&C&D\\ \hline A&-&4&12&\infty\\ B&\infty&-&3&10\\ C&\infty&\infty&-&2\\ D&6&\infty&\infty&- \end{array}

The route table is

\mathbf R^{(0)}= \begin{array}{c|cccc} &A&B&C&D\\ \hline A&A&B&C&D\\ B&A&B&C&D\\ C&A&B&C&D\\ D&A&B&C&D \end{array}

Why is row $B$ , column $A$ infinite despite $A\to B$ existing? The road has only the direction $A$ to $B$ ; reversing it would invent an arc.

Answer. The two initial tables are displayed above.

Check. Exactly six off-diagonal distance entries are finite, matching the six directed arcs. The table is not symmetric.

Worked example 2 changes only $D\to A$ , from weight $6$ to weight $9$ . Its reverse entry is still unavailable.

Worked example 2: changing one directed weight

Question. Construct the initial tables for the same network when $D\to A$ has weight $9$ .

Plan. Change only row $D$ , column $A$ of the distance table; retain the next-hop initialisation.

\mathbf D^{(0)}= \begin{array}{c|rrrr} &A&B&C&D\\ \hline A&-&4&12&\infty\\ B&\infty&-&3&10\\ C&\infty&\infty&-&2\\ D&9&\infty&\infty&- \end{array}

\mathbf R^{(0)}= \begin{array}{c|cccc} &A&B&C&D\\ \hline A&A&B&C&D\\ B&A&B&C&D\\ C&A&B&C&D\\ D&A&B&C&D \end{array}

Why does the route table not change? The direct $D$ -to- $A$ route still has $A$ as its next node; only its cost changed.

Answer. The distance entry $d_{DA}$ is $9$ , while $d_{AD}$ remains $\infty$ ; the initial route table is unchanged.

Check. The six directed connections are the same. A weight change has neither added a road nor reversed one.

A question may supply the tables rather than the network. Read its symbols and node order before starting; a matrix of direct connections and a completed matrix of shortest distances serve different purposes.

Watch out

Wrong: mirror a one-way arc across the diagonal, or put zero for a missing road. Right: row-to-column direction controls the entry, and an unavailable direct arc is $\infty$ .

Change the same directed weight again.

Completing the iterations

Unless directed otherwise, use $A$ as the first pivot, then $B$ , then $C$ , then $D$ . At each iteration, the pivot's row and column stay unchanged; use them to test every other origin-destination pair.

Floyd's distance and next-hop updates

At the iteration using pivot node $k$ , compare the current route $i$ to $j$ with going via $k$ :

d_{ij}^{\mathrm{new}}= \min\!\left(d_{ij}^{\mathrm{old}},\ d_{ik}^{\mathrm{old}}+d_{kj}^{\mathrm{old}}\right)

If the candidate is strictly smaller, replace the distance and copy

r_{ij}^{\mathrm{new}}=r_{ik}^{\mathrm{old}}

Otherwise retain both entries. Treat a diagonal dash as $0$ , and $\infty$ plus a finite number as $\infty$ .

Not in the formula booklet: learn it.

Why copy $r_{ik}$ , not simply write $k$ ? The first leg from $i$ to $k$ may already be an indirect route. Its first step is the first step of the new complete route too. On an equal distance, retaining the old route entry keeps one consistent shortest route.

[DIAGRAM: asset_name: Testing an entry using a pivot row and column; asset_slug: 9fm0-d1-168-pivot-update; caption: At the B iteration, D to C improves from 18 to 13, but its next hop remains A.; description: The distance table after the A iteration has row B and column B shaded; the calculation D to B10 plus B to C3 gives13 instead of18, with next-hop copying from row D column B equal to A.]

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure Mathematics

Further Pure Mathematics 1

Further Pure Mathematics 2

Further Statistics 1

Further Statistics 2

Further Mechanics 1

Further Mechanics 2

Decision Mathematics 1

Decision Mathematics 2

D1 2.2 - Floyd's algorithm

All pairs of nodes, not one starting node

Constructing the initial tables

Completing the iterations

Continue this lesson.

Learn faster with Nova