Question

Unfortunately, the road from Fordyce and Sheridan is closed due to dangerous road conditions caused by the recent bad weather. Find the shortest route between each pair of towns

Answer 1

a) Malvern - Sheridan - Pine Bluff

b) Camden - Fordyce - Pine Bluff

c) Benton - Malvern - Sharidan - Arkadepia

d) Benton - Malvern - Sharidan - Arkadepia - Gurden - Camden - Fordyce

e) Benton - Malvern - Sharidan - Arkadepia - Gurden - Camden

Explanation:

P.S - The exact question is -

Given - According to a map of Arkansas, a number of good roads connect

some of the towns south of Little Rock. The road between

Malvern and Benton is 23 miles long, and between Benton and Pine

Bluff is 62 miles long. The road between Malvern and Sheridan is

28 miles long, and then from Sheridan to Pine Bluff is 22 miles

long. Arkadelphia is connected to two towns: it is 12 miles from

Gurden and 21 miles from Sheridan. Fordyce has three roads to

these towns: 45 miles to Pine Bluff, 39 miles to Sheridan, and 27

miles to Camden. The road from Gurden to Camden is 38 miles.

To find - Unfortunately, the road from Fordyce to Sheridan is closed due to

dangerous road conditions caused by the recent bad weather. Find

the shortest route between each pair of towns:

a) Malvern and Pine Bluff

b) Camden and Pine Bluff

c) Benton and Arkadelphia

d) Fordyce and Malvern

e) Benton and Camden

Proof -

The figure is as follows :

a)

Shortest route between Malvern and Pine Bluff :

Firstly, put all the vertices to ∞

Start from Malvern ,

Check the shortest distance from the corresponding vertices of Malvern.

Shortest Distance = min { Malvern - Benton, Malvern -Sheridan }

= min { 23, 28 } = 23

⇒Shortest distance is 23 ( Malvern -Benton )

Now,

Check shortest distance from Benton and Malvern

Shortest Distance = min { Benton - Pine Bluff, Malvern -Sheridan }

= min { 62, 28 } = 28

⇒Shortest distance is 28 ( Malvern -Sheridan )

Now,

Check shortest distance from Benton and Sheridan

Shortest Distance = min { Benton - Pine Bluff, Sheridan - Pine-Bluff}

= min { 85, 50 } = 50

⇒Shortest distance is 50 ( Sheridan - Pine-Bluff )

So,

By back tracking , we get

Shortest Route be -

Malvern - Sheridan - Pine Bluff

And the Shortest distance be = 50 miles

b)

Shortest Route between Camden and Pine Bluff

From Camden -

Shortest Distance = min {Camden-Fordyce, Camden-Gurden }

= min { 27, 38 } = 27

⇒Shortest Distance = 27 (Camden-Fordyce )

Now,

Check Shortest distance from Camden and Fordyce

Shortest Distance = min { Camden-Gurden, Fordyce-Pine Bluff }

= min { 38, 72 } = 38

⇒Shortest Distance = 38 ( Camden-Gurden )

Now,

Check Shortest Distance from Gurden and Fordyce

Shortest Distance = min { Gurden-Arkadepia, Fordyce-Pine Bluff }

= min { 50, 72 } = 50

⇒Shortest Distance = 50 ( Gurden-Arkadepia )

Now,

Check Shortest Distance from Arkadepia and Fordyce

Shortest Distance = min { Arkadepia - Sharidan, Fordyce-Pine Bluff }

= min { 71, 72 } = 71

⇒Shortest Distance = 71 ( Arkadepia - Sharidan )

Now,

Check Shortest Distance from Sharidan and Fordyce

Shortest Distance = min { Sharidan - Pine Bluff , Fordyce-Pine Bluff }

= min { 93, 72 } = 72

⇒Shortest Distance = 72 ( Fordyce-Pine Bluff )

So, By Back tracking , we get

Shortest route be

Camden - Fordyce - Pine Bluff

Shortest Distance be 72 miles

c)

Shortest route between Benton and Arkadelphia

By applying the same method ,

If we start from Benton and by using Pine bluff lane, distance be 62 + 45 + 27 + 38 + 12 = 184 miles

And

If we start from Benton and by using Malvern lane, distance be 23 + 28 + 21 = 72 miles

So,

Shortest Route be -

Benton - Malvern - Sharidan - Arkadepia

Shortest distance be 72 miles

d)

Shortest route between Fordyce and Malvern

By applying the same method ,

If we start from Malvern and by using Benton lane, distance be 23 + 62 + 45 = 130 miles

And

If we start from Malvern and by using Sharidan lane, distance be 28 + 21 + 12 + 38 + 27 = 126 miles

So,

Shortest Route be -

Benton - Malvern - Sharidan - Arkadepia - Gurden - Camden - Fordyce

Shortest distance be 126 miles

e)

Shortest route between Benton and Camden

By applying the same method ,

If we start from Benton and by using Pine Bluff lane, distance be 62 + 45 + 27 = 134 miles

And

If we start from Benton and by using Malvern lane, distance be 23 + 28 + 21 + 12 + 38 = 122 miles

So,

Shortest Route be -

Benton - Malvern - Sharidan - Arkadepia - Gurden - Camden

Shortest distance be 122 miles