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

Question

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

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

По какой-то причине, когда я пытаюсь удалить текущий узел из Непосещенных набора с помощью 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'] 

Обратите внимание, что ток является значение извлекается из список, а 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 

Answer 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. Если вы предпочитаете обрабатывать влево-вправо, вы должны использовать collections.deque класс:

import collections 

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

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

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

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

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

  TestFile = г «C: \ Новая папка»

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