Djisktra algo implementation returning array of all same values

user_8518689 0
Viewed 42

This is a solution to city problem, where cities have at most 1 train station and 1 bus station, some cities have both. and from a starting city i will be finding all the shortest paths to other cities. For that I am running this code and trying to get the all shortest paths from every city, but without the recursion i get this object down below.

visitedCities = []
Cities = {"Istanbul" : 0, "Bursa" : 0, "Eskisehir" : 0}

totalCostsSaved = {"Istanbul" : Cities, "Bursa" : Cities, "Eskisehir" : Cities}

#To find Quickest Itenaries from city, just set these variables Istanbul-Bus instead of istanbul-harem for example
startCity = "Istanbul" #City C 
startStation = "Bus" #Station of City


StationAverageTimeChange = { "Istanbul" : 30, "Eskisehir" : 10}

Bus = { "Istanbul-Bursa" : 100, "Bursa-Eskisehir" : 120 }
Train = { "Istanbul-Eskisehir" : 180 }

CitiesWithTrain = ["Istanbul", "Eskisehir"]
CitiesWithBus = ["Istanbul", "Bursa", "Eskisehir"]


def getCostToDestination(currentCity, currentStation, currentCost):
    for city in totalCostsSaved.keys():
        newCities = Cities
        if currentCity == city:
          continue
        
        if currentStation == "Bus" and currentCity in CitiesWithTrain: #check if trainStationExists
          for cityPairs in Train.keys():
            if currentCity in cityPairs.split("-"):
              for cit in cityPairs.split("-"):
                if cit != currentCity:
                  costToNewCity = currentCost + Train[cityPairs] + StationAverageTimeChange[currentCity]
                  if totalCostsSaved[currentCity][cit] == 0 or costToNewCity < totalCostsSaved[currentCity][cit]:
                    totalCostsSaved[currentCity][cit] = costToNewCity
                    if cit not in visitedCities:
                        visitedCities.append(cit)
          for cityPairs in Bus.keys():
            if currentCity in cityPairs.split("-"):
              for cit in cityPairs.split("-"):
                if cit != currentCity:
                  costToNewCity = currentCost + Bus[cityPairs]
                  if totalCostsSaved[currentCity][cit] == 0 or costToNewCity < totalCostsSaved[currentCity][cit]:
                    totalCostsSaved[currentCity][cit] = costToNewCity
                    if cit not in visitedCities:
                      visitedCities.append(cit)



        if currentStation == "Train" and currentCity in CitiesWithBus: #check if bus
          for cityPairs in Bus.keys():
              if currentCity in cityPairs.split("-"):
                for cit in cityPairs.split("-"):
                  if cit != currentCity:
                    costToNewCity = currentCost + Bus[cityPairs] + StationAverageTimeChange[currentCity]
                    if totalCostsSaved[currentCity][cit] == 0 or costToNewCity < totalCostsSaved[currentCity][cit]:
                      totalCostsSaved[currentCity][cit] = costToNewCity
                      if cit not in visitedCities:
                        visitedCities.append(cit)
          for cityPairs in Train.keys():
              if currentCity in cityPairs.split("-"):
                for cit in cityPairs.split("-"):
                  if cit != currentCity:
                    costToNewCity = currentCost + Train[cityPairs]
                    if totalCostsSaved[currentCity][cit] == 0 or costToNewCity < totalCostsSaved[currentCity][cit]:
                      totalCostsSaved[currentCity][cit] = costToNewCity
                      if cit not in visitedCities:
                        visitedCities.append(cit)

        


getCostToDestination(startCity, startStation, 0)


print(totalCostsSaved)

When I run this, I get

{'Istanbul': {'Istanbul': 0, 'Bursa': 100, 'Eskisehir': 210}, 'Bursa': {'Istanbul': 0, 'Bursa': 100, 'Eskisehir': 210}, 'Eskisehir': {'Istanbul': 0, 'Bursa': 100, 'Eskisehir': 210}}

But I am supposed to get

{'Istanbul': {'Istanbul': 0, 'Bursa': 100, 'Eskisehir': 210}, 'Bursa': {'Istanbul': 0, 'Bursa': 0, 'Eskisehir': 0}, 'Eskisehir': {'Istanbul': 0, 'Bursa': 0, 'Eskisehir': 0}}

How do I fix this, if i do recursive they all have the same values whereas they should be different.

dijkstra python-3.x python
1 Answers

The reason you are getting that result is because you are using the dictionary Cities as the value to each key in the totalCostsSaved dict, and since a dict is a mutable object updating one updates them all.

totalCostsSaved = {"Istanbul" : Cities, "Bursa" : Cities, "Eskisehir" : Cities}

For Example:

If you were to: totalCostsSaved['Istanbul']['Bursa'] = 100

That assignment will also adjust totalCostsSave['Bursa']['Bursa'] and totalCostsSave['Eskiesehir']['Bursa'] because they all using the same shared dictionary..

One way to avoid this would be to create new dictionaries for each key. For example:

totalCostsSaved = {
    "Istanbul" : {
        "Istanbul" : 0,
        "Bursa" : 0,
        "Eskisehir" : 0
    },
    "Bursa" : {
        "Istanbul" : 0,
        "Bursa" : 0,
        "Eskisehir" : 0
    },
    "Eskisehir" : {
        "Istanbul" : 0,
        "Bursa" : 0,
        "Eskisehir" : 0
    }
}

Another way would be to make unique copy them:

from copy import copy
totalCostsSaved = {
    "Istanbul" : copy(Cities), 
    "Bursa" : copy(Cities), 
    "Eskisehir" : copy(Cities)
}

Both of these options creates a unique dictionary so when updating the values it will not effect the others.

user_178294510
Related