Suppose that you operate Cheapo Air. a service company that finds the cheapest f

Question

Suppose that you operate Cheapo Air. a service company that finds the cheapest flight(s) from Cheapo Airlines from any city to any city served by flights from Cheapo Airlines, for your clients. A very poor student comes in and tells you that they would like to fly from San Francisco to New York spending the least amount that they possibly can. Find a set of flights that will satisfy the student. Suppose that there are flights from San Francisco to Sacramento and San Jose costing $12 and $20; from Sacramento to Salt Lake City and San Jose, costing $100 and $7; from San Jose to Salt Lake City and Denver costing $80 and $95; from Denver to Miami and Atlanta costing $80 and $70; Salt Lake City to Charleston, and Miami costing $80 and $100; Miami to Charleston, Atlanta and New York costing $20, $20, and $50Charleston to New York costing $68; and Atlanta to New York costing $58. Cheapo Airlines operates all these flights every 3 hours, every day, day and night. How much does your student have to spend to fly from San Francisco to New York using Cheapo Airlines flights? Use Dijkstra's algorithm to solve the problem.

Explanation / Answer

1) Using Dijkstra's Algorithm we will get the overall lowest fare to the student as 242.

San Francisco>Sacramento(12)>San Jose(19)>Denver(114)>Atlanta(184)>Newyork(242).

As  San Francisco to Sacramento(12)

Sacramento to San Jose(7)

San Jose to Denver(95)

Denver to Atlanta(70)

Atlanta to Newyork(58).

2) If there is a negative cost arc then we will get incorrect result becuase if we once mark or close the cost between 2 vertices then we cant update it.

  

  

  

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.