Djisktra algo实现返回所有相同值的数组

Question

这是解决城市问题的一个办法，城市最多有一个火车站和一个公共汽车站，有些城市则两者兼有。从一个开始的城市，我将找到通往其他城市的所有最短的道路。为此，我正在运行这段代码，并试图从每个城市获得所有最短的路径，但是没有递归，我会在下面得到这个对象。

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)

当我运行这个，我得到

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

但我应该

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

如何解决这个问题，如果我进行递归，它们都有相同的值，而它们应该是不同的。

Answer 1

您之所以得到这个结果，是因为您使用字典Cities作为totalCostsSaved dict中每个键的值，而且由于dict是一个可变对象，因此可以更新它们。

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

例如：

如果你要：totalCostsSaved['Istanbul']['Bursa'] = 100

该赋值还将调整totalCostsSave['Bursa']['Bursa']和totalCostsSave['Eskiesehir']['Bursa']，因为它们都使用相同的共享字典。

避免这种情况的一种方法是为每个键创建新的字典。例如：

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

另一种方法是复制它们：

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

这两个选项都会创建一个唯一的字典，因此在更新值时不会影响其他选项。