0

我希望你能帮我解决一些困扰我的事情。我真的试图自己解决这个问题，但几个小时后，我觉得完全卡住了。

所以，我是 python（我的第二语言）的新手，我正在编写一个 Dijkstra 算法的实现，作为我本科研究的一部分。

出于某种奇怪的原因，当我尝试使用 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
4

1 回答 1

0

您的代码基本上是这样做的：

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

此外，还有一些关于您的代码的风格挑剔：

  • 您的代码违反了 PEP 8 编码风格指南。您的变量应使用 words_separated_by_underscores 命名。只有当它们是类名时，它们才应该以大写字母开头。请参阅http://www.python.org/dev/peps/pep-0008/#global-variable-names。（我建议的类 deque 也违反了本指南，但我认为这是因为它是在 Python 的早期阶段创建的，在 PEP 8 被广泛接受之前，并且由于向后兼容性而无法更改。为什么它是在 Py3K 中没有改变，我不知道。）

  • 您对反斜杠的使用也值得怀疑。对于包含反斜杠的字符串，您应该使用 Python 的原始字符串功能，如下所示：

    testfile = r"c:\新文件夹"

替代方法包括使用正斜杠（Windows 文件系统使用它们）、使用 os.path.join 以实现跨平台兼容性、在命令行参数中接受文件名或使用双反斜杠。

于 2013-03-14T05:38:07.470 回答