4. (20 points) Single-Source Shortest Path. It\'s Christmas vacation. Your favor

Question

4. (20 points) Single-Source Shortest Path. It's Christmas vacation. Your favorite aunt surprises you with a nice big check. With the extra money, you plan to visit Granny in New York City on Christmas day, but you have plenty of time and would like to visit other relatives along the way. You've got a free ride to Seattle, but from there, you have to pay 50 cents for every mile you fly. Given the map below with the location of all of your relatives and the distances between them, what's your best option for getting to Granny's and how much will it cost? SEA- 1500 SEA1500 1S 1000 800 800 LGA SFO 1200 400 1800 STL 1500 400 LAX 1500 DFW 1000 MIA)

Explanation / Answer

Apply Dijkstra's algorithm to find the path from seattle to every city with least cost

Here is Python Code

import sys
import heapq

def disktra(l,n,st):
    visit = [False]*n
    final = [True]*n
    dist = [sys.maxint]*n
    dist[st] = 0
    heap = []
    heapq.heappush(heap,(0,st))
    while (cmp(visit,final) != 0):
        best = heapq.heappop(heap)[1]
        visit[best] = True
        t = 0
        for ch in l[best]:
            if (visit[ch[0]] == False and dist[best] + ch[1] < dist[ch[0]]):
                dist[ch[0]] = dist[best] + ch[1]
                heapq.heappush(heap,(dist[ch[0]],ch[0]))
        if (len(heap) == 0):
            break

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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