Converting a Network into a Network of Least Distances

It's only fair to share...Share on FacebookTweet about this on TwitterPin on PinterestShare on Google+Share on RedditEmail this to someone

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.

Comments are closed.