Python Dijkstra: удаление текущего узла из невидимой ошибки: list.remove(x): x отсутствует в списке

Я хотел бы, чтобы вы помогли с чем-то, что меня беспокоило. Я действительно пытался понять это самостоятельно, но через несколько часов я чувствую себя полностью застрявшим.

Итак, я новичок в python (мой второй язык), и я пишу реализацию алгоритма Дейкстры как часть моего исследования студентов.

По какой-то странной причине, когда я пытаюсь удалить текущий узел из невидимого набора с помощью Unvisited.remove(Current), я получаю следующую ошибку:

Traceback (most recent call last):
Current Node: 
  File "H:\DijkstraShortestPath\src\Main.py", line 92, in <module>
    Unvisited.remove(Current)
ValueError: list.remove(x): x not in list
1
Unvisited Nodes: 
['1', '2', '3', '4', '5', '6', '7', '8']
Current Node: 
8
Unvisited Nodes: 
['2', '3', '4', '5', '6', '7', '8']

Обратите внимание, что Current - это значение, извлеченное из списка, а Unvisited - это список.

Посмотрев несколько веток здесь и изучив весь Интернет, я решил опубликовать весь код, чтобы избежать путаницы. Я заметил какую-то проблему с list.remove(x), когда он вложен в циклы (мой тоже вложен в цикл for), но я не понимаю, что происходит под всем техно-жаргоном.

Может кто-нибудь объяснить мне, почему это проблема? Что я могу сделать, чтобы это исправить?

#Main File
#Excecutes the Dijkstra Shortest Path Algorithm

#import Create_Network #Generates Network with 5 OD pairs as replications

testfile = "\DijkstraShortestPath\Backup And Tests\TEST"
Arcfile = testfile + "\Arcs.txt"
ODfile = testfile + "\ODpairs.txt"
Nodefile = testfile + "\Nodes.txt"

#INITIALIZE ALGORITHM
#Populate label, visited, and unvisited sets
#For initial conditions, label is infinite for all nodes except origin
#For initial conditions, all nodes are unvisited (including origin)

LabelArray = [] #Stores the distance labels for each of the nodes; has length
                #equal to the number of nodes in the network
Unvisited = [] #Stores unvisited nodes, by NodeID
Visited = [] #Stores visited nodes, by NodeID
ODArray = [] #Stores Origin and Destination Pairs

#Get the origin and destination pair
with open(ODfile,'r') as f:
    for line in f:
        ODArray = line.strip().split(",")
Origin = ODArray[0]
Destination = ODArray[1]
#Set the first current node as the origin
Current = Origin

#Generate Unvisited nodes and Labels (all infinite, except origin)
with open(Nodefile,'r') as f:
    for line in f:
        LabelArray.append(float("inf")) #make all node distance labels infinite
        NodeID = line.strip().split(",")[0]
        Unvisited.append(NodeID) #Add NodeID to Unvisited

#Set distance for origin to zero
LabelArray[int(ODArray[0])-1] = float(0) #float(0) to match float("inf")

#Count number of lines and items in each line
#i.e., find out how many nodes and params for storage in ArcParams list
numarcs = 0
with open(Arcfile,'r') as f:
    for line in f:
        if line != '\n':
            numarcs = numarcs + 1 #integer
            numparams = len(line.strip().split(",")) #integer

#Store arc origin, destination, length to ArcParams list
ArcParams = [[0 for i in range(numparams)] for i in range(numarcs)]

with open(Arcfile,'r') as f:

    for line in f:
        params = line.strip().split(",")
        ArcParams[int(params[0])-1][0] = params[0]
        ArcParams[int(params[0])-1][1] = params[1]
        ArcParams[int(params[0])-1][2] = params[2]
        ArcParams[int(params[0])-1][3] = float(params[3])

#END INITIALIZATION

#BEGIN DIJKSTRA SHORTEST PATH, LOOPING OVER NODES IN NETWORK

for node in Unvisited:

    #Find the nodes adjacent to Current AND in Unvisited
    Adjacent = []

    for i in range(numarcs):
        if ArcParams[i][1] == Current: #search for origin = current
            if ArcParams[i][1] in Unvisited: #checks if nodes found are in Unvisited
                if ArcParams[i][1] != ArcParams[i][2]: #excludes Current as adjacent
                    Adjacent.append(ArcParams[i][2]) #Add node to Adjacent

    #For each adjacent node, update distance labels

    for node in Adjacent:
        temp = float(LabelArray[int(Current)-1]) + float(ArcParams[int(node)][3])

        if temp < LabelArray[int(node)-1]:
            LabelArray[int(node)-1] = temp

    #Add current node to Visited set
    print "Current Node: "
    print Current
    print "Unvisited Nodes: "
    print Unvisited

    Visited.append(Current)
    Unvisited.remove(Current)

    #Check for end-conditions; has destination entered Visited?
    #Or is the smallest tentative distance infinite? Stop both ways.

    if Destination in Visited:
        if LabelArray[int(Destination)-1] == inf:
            print "There is no feasible path"
        print "Shortest distance found!"
        print "Distance is: " + str(LabelArray[Destination-1])


    #Select the Unvisited node marked with smallest tentative distance
    MinDist = min(LabelArray[1:])
    MinNode = LabelArray.index(MinDist) + 1

    #Clear existing Current, set new Current
    Current = MinNode

1 ответ

Ваш код по существу делает это:

for item in container:
    # stuff
    container.remove(item)
    # more stuff

Изменение контейнера во время его итерации обычно нарушает ваш код. В стандартной библиотеке Java есть специальное исключение (ConcurrentModificationException), которое обычно заставляет вашу программу справиться с такой проблемой, но, к сожалению, Python этого не делает; ваша петля просто сделает неправильную вещь.

Ситуация здесь напоминает старую шутку, пациент: "Мне больно, когда я так поступаю". Доктор: "Не делай этого".

Попробуйте что-то вроде этого:

container = [6, 7, 8]

while len(container) > 0:
    item = container.pop()
    # do something useful with item

Это обрабатывает последний использованный элемент первым. Так, например, первая итерация даст вам 8, затем 7, а затем 6. Если вы предпочитаете обрабатывать слева направо, вы должны использовать класс collection.deque:

import collections

container = collections.deque([6, 7, 8])

while len(container) > 0:
    item = container.popleft()
    # do something useful with item

Кроме того, пара стилей о вашем коде:

  • Ваш код нарушает руководство по стилю кодирования PEP 8. Ваши переменные должны быть названы словами words_separated_by_underscores. Они должны начинаться с заглавной буквы, только если они являются именами классов. См. http://www.python.org/dev/peps/pep-0008/. (Класс, который я предложил, deque, также нарушает это руководство, но я предполагаю, что это потому, что он был создан в очень ранние дни Python, до того, как PEP 8 получил широкое признание, и не мог быть впоследствии изменен из-за обратной совместимости. Почему это не было не изменилось в Py3K, я понятия не имею.)

  • Использование обратной косой черты также сомнительно. Вы должны использовать функцию необработанных строк Python для строк, которые содержат обратную косую черту, например:

    testfile = r "c: \ new folder"

Альтернативные варианты включают использование прямых косых черт (их используют файловые системы Windows), использование os.path.join для кросс-платформенной совместимости, принятие имени файла в аргументах командной строки или использование двойной обратной косой черты.

Другие вопросы по тегам