Converting a Network Into a Network of Least Distances
Given a network, it is desirable to construct a table showing the minimum distance between any two vertices in the network – this includes the case where vertices are not directly connected. We find the least distance even for indirectly connected verticesFor example given the network below,
We can go direct from A to C (distance 9), or A to C via B (distance 4+2=6), or from A to C via E (distance 5+3=8), or from A to C via E and D (distance 5+1+3=9), or from A to C via D (distance 7+3=10). The least of all these distance is 6, using the route A to C via B. Gong the the whole network in this way gives us the least distance matrix below.
A | B | C | D | E | |
A | - | 4 | 6 | 6 | 5 |
B | 4 | - | 2 | 5 | 5 |
C | 6 | 2 | - | 3 | 3 |
D | 6 | 5 | 3 | - | 1 |
E | 5 | 5 | 3 | 1 | - |
Notice that the only blank spaces are between vertices and themselves.