iamsahinemir
iamsahinemir

Reputation: 9

How can I add one stop point to the distance between two cities in the Dijkstra algorithm?

In a project at school, the teacher gave us 10 cities and their pairwise distances, and asked us to find the minimum distance from Izmir to Van but with the following restriction:

You start from İzmir visit some of the other 8 cities on the way and reach to Van, where you stay exactly one night in an intermediate city, move to another one next morning and reach there in the same evening. You may come back to the same intermediate city. What is the minimum distance you must travel for such a task (including at least one night-stay)?

He asked us to solve this problem using the Dijkstra algorithm. I wrote the algorithm with Python without adding stops. The code is below:

import heapq

# Distance calculation function.
def distance_calculation_for_cities(cities, starting_node):
    distances = {node: float('infinity') for node in cities}
    distances[starting_node] = 0

    hq = [(0, starting_node)]

    while len(hq) > 0:
        current_distance, current_node = heapq.heappop(hq)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in cities[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(hq, (distance, neighbor))

    return distances

# Array for our cities.
cities = {
    'Izmir': {'Ankara': 584, 'Antalya': 448, 'Denizli': 234, 'Erzurum':1468, 'Gaziantep':1123, 'Gümüşhane':1354, 'İstanbul':566, 'Izmir':0, 'Van':1750, 'Bayburt':1407},
    'Ankara': {'Ankara': 0, 'Antalya': 542, 'Denizli': 477, 'Erzurum':876, 'Gaziantep':647, 'Gümüşhane':762, 'İstanbul':453, 'Izmir':584, 'Van':1212, 'Bayburt':815},
    'Antalya': {'Ankara': 542, 'Antalya': 0, 'Denizli': 227, 'Erzurum':1244, 'Gaziantep':763, 'Gümüşhane':1172, 'İstanbul':715, 'Izmir':448, 'Van':1447, 'Bayburt':1183},
    'Denizli': {'Ankara': 477, 'Antalya': 227, 'Denizli': 0, 'Erzurum':1336, 'Gaziantep':978, 'Gümüşhane':1248, 'İstanbul':650, 'Izmir':234, 'Van':1605, 'Bayburt':1275},
    'Erzurum': {'Ankara': 876, 'Antalya': 1244, 'Denizli': 1336, 'Erzurum':0, 'Gaziantep':652, 'Gümüşhane':763, 'İstanbul':1098, 'Izmir':1123, 'Van':684, 'Bayburt':125},
    'Gaziantep': {'Ankara': 647, 'Antalya': 763, 'Denizli': 978, 'Erzurum':652, 'Gaziantep':0, 'Gümüşhane':763, 'İstanbul':1098, 'Izmir':1123, 'Van':684, 'Bayburt':730},
    'Gümüşhane': {'Ankara': 762, 'Antalya': 1172, 'Denizli': 1248, 'Erzurum':211, 'Gaziantep':763, 'Gümüşhane':0, 'İstanbul':1086, 'Izmir':1354, 'Van':618, 'Bayburt':86},
    'İstanbul': {'Ankara': 453, 'Antalya': 715, 'Denizli': 650, 'Erzurum':1229, 'Gaziantep':1098, 'Gümüşhane':1086, 'İstanbul':0, 'Izmir':566, 'Van':1636, 'Bayburt':1126},
    'Bayburt': {'Ankara': 815, 'Antalya': 1183, 'Denizli': 1275, 'Erzurum':125, 'Gaziantep':730, 'Gümüşhane':86, 'İstanbul':1126, 'Izmir':1407, 'Van':532, 'Bayburt':0},
    'Van': {'Ankara': 1212, 'Antalya': 1447, 'Denizli': 1605, 'Erzurum':410, 'Gaziantep':684, 'Gümüşhane':618, 'İstanbul':1636, 'Izmir':1750, 'Van':0, 'Bayburt':532},
    
}

Question 1. Minimum distance for Izmir to Van.

print(distance_calculation_for_cities(cities, 'Izmir'))

We need to change this code as I mentioned above. Is there anyone who can help?

Upvotes: 0

Views: 88

Answers (0)

Related Questions