Dijkstra的alghoritm在python中的奇怪行为

Question

我正在用python实现dijkstra的alghoritm。我想知道从节点“You”到所有其他节点的长度。你知道吗

def Dijkstr():
    listOfProcessingNodes = listOfNodes
    for i in listOfNodes:
        if i.name == "You":
            i.lastNode = None
            i.length = 0
            i.resolved = True
            lastProcessNode = i

    listOfProcessingNodes.sort(key=lambda x: x.length, reverse=True)

    while len(listOfProcessingNodes):
        processNode = listOfProcessingNodes.pop()
        for i in processNode.adjencyList:
            for k in listOfEdges:
                if (k.inNode == i.name and k.outNode == processNode.name and i.resolved == False) or (k.inNode == processNode.name and k.outNode == i.name and i.resolved == False):
                    i.length = processNode.length + int(float(k.cost))
                    i.lastNode = processNode
                    i.resolved = True
        listOfProcessingNodes.sort(key=lambda x: x.length, reverse=True)
        lastProcessNode = processNode
        print processNode.name,":", processNode.length

以下是节点和边类的定义：

class Node():
    def __init__(self, name):
        self.name=name
        self.adjencyList=[]
        self.resolved = False
        self.lastNode = None
        self.length = float("inf")

class Edge():
    def __init__(self, inNode, outNode, cost):
        self.inNode=inNode
        self.outNode=outNode
        self.cost=cost

供我参考

You - A: 3
You - B: 2
A - C: 4
A - D: 4
B - D: 1
B - E: 2
C - F: 1
D - F: 2
D - G: 4
E - G: 2
F - G: 2

我得到这个输出

You : 0
B : 2
A : 3
D : 3
E : 4
F : 5
C : 7
G : 7

而不是

You : 0
B : 2
A : 3
D : 3
E : 4
F : 5
C : 6
G : 6

我真的很困惑，如果它不适用于所有节点，那么我会出错，但如果它不适用于最后2个节点？谢谢你的帮助

Answer 1

你似乎误解了Dijkstra算法的一个关键部分。你知道吗

随着算法的进行，如果算法找到一条比以前找到的路由“便宜”的路径，则节点的“长度”（即“You”节点的最小总“成本”）可能会减少。您的代码假设一旦一个节点被访问一次，它的长度就固定了。这是不正确的。你知道吗

您的图表包含这样一种情况，即发生这种情况。当访问节点D时，长度为3，则F的长度为5，G的长度为7。但是，当访问长度为4的节点E时，需要将G的长度减少到6，因为E的长度为4，而从E到G的边的成本为2。你知道吗

与其过滤掉resolved设置为True的任何节点，不如检查processNode的长度加上边k的开销是否小于节点i的当前已知长度。如果是这样，您已经为节点i找到了一个新的较低长度，因此应该更新节点i及其以前节点的长度。你知道吗

顺便说一下，节点C的长度应该是7，而不是您所声称的6。你知道吗