python 中 Dijkstra 算法的奇怪行为

Question

我正在尝试在 python 中实现 dijkstra 的算法。我想知道从节点 "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 算法的一个关键部分有误解。

随着算法的进行，如果算法找到路径，节点的'length'（即'You'节点的最小总数'cost'）可能会减少到那个比以前找到的节点 'cheaper' 的节点。您的代码假定一旦一个节点被访问过一次，它的长度就固定了。这是不正确的。

您的图表包含发生这种情况的一种情况。当访问长度为 3 的节点 D 时，然后给 F 的长度为 5，G 的长度为 7。但是，当访问长度为 4 的节点 E 时，需要将 G 的长度减少到 6，因为 E 有长度4 并且从 E 到 G 的边成本为 2.

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

顺便说一句，节点C的长度应该是7，而不是你说的6。

python 中 Dijkstra 算法的奇怪行为

Strange behavior of Dijkstra's alghoritm in python

python

graph

dijkstra