Operation Research , minimum spanning path, transportation Problems. Plz show al

ID: 1721585 • Letter: O

Question

Operation Research , minimum spanning path, transportation Problems. Plz show all your work in a paper!

A truck must travel from New York to Los Angeles. As shown in the diagram below, a variety of routes are available. The number associated with each arc is the number of gallons of fuel required by the truck to travel to that city. Use the shortest- path algorithm to find the route from New York to Los Angeles that used the minimum amount of gas. 1800 ClevelandPhoenix 900 400 400 900 1100 950 Los Angeles 600 1300 New York St. Louis Dallas 1000 600 800 Nashville Salt Lake City

Explanation / Answer

The table below provides the various possible routes from NY to LA and the corresponding amount of gas required to travel.

Route from New York to Los Angeles

Amount of gas required

NY ---> C ---> P ---> LA

400 + 1800 + 400 = 2600

NY ---> C ---> D ---> LA

400 + 900 + 1300 = 2600

NY ---> C ---> D ---> P ---> LA

400 + 900 + 900 + 400 = 2600

NY ---> C ---> D ---> SLC ---> LA

400 + 900 + 1000 + 600 = 2900

NY ---> SL ---> D ---> LA

950 + 600 + 1300 = 2850

NY ---> SL ---> D ---> P ---> LA

950 + 600 + 900 + 400 = 2850

NY ---> SL ---> D ---> SLC ---> LA

950 + 600 + 1000 + 600 = 3150

NY ---> SL ---> P ---> LA

950 + 1100 + 400 = 2450

NY ---> N ---> SLC ---> LA

800 + 1200 + 600 = 2600

NY ---> N ---> D ---> LA

800 + 600 + 1300 = 2700

NY ---> N ---> D ---> P ---> LA

800 + 600 + 900 + 400 = 2700

NY ---> N ---> D ---> SLC ---> LA

800 + 600 + 1000 + 600 = 3000

Where NY = New York, C = Cleveland, P = Phoenix, LA = Los Angeles, SL = St. Louis, D = Dallas, N = Nashville, SLC = Salt Lake City.

Using the shortest path algorithm, the route from NY to LA that used the minimum amount of gas is

NY ---> SL ---> P ---> LA (highlighted in the table above as this route used the minimum amount of gas among the other routes).