最短路径未返回正确解决方案

Question

一直在尝试在用户定义图中实现Dijkstras算法。但它总是给出错误的解决方案。不管怎样你们能帮我看看吗？你知道吗

I have been trying to use this graph as my test graph where A is the start Node and G is the end node. It should return the path A,C,D,F,G, but it actually returns A,B,D,E,G. For some reason it skips out the C...

 def ShortestPath(self, Source, Dest):
    Distances = {}
    Previous = {}

    for EachNode in self.NodeList.keys():
        Distances[EachNode] = -1
        Previous[EachNode] = ""

    Distances[Source] = 0
    UnseenNodes = self.NodeList.keys()
    while len(UnseenNodes) > 0:
        ShortestDistance = None
        Node = ""
        for TempNode in UnseenNodes:
            if ShortestDistance == None:
                ShortestDistance = Distances[TempNode]
                Node = TempNode
            elif Distances[TempNode] < ShortestDistance:
                ShortestDistance = Distances[TempNode]
                Node = TempNode
        UnseenNodes.remove(Node)

        for Neighbour, NeighbourValue in self.NodeList[Node].Connections.items():
            NeighbourID = Neighbour.GetID()
            print NeighbourID
            if Distances[NeighbourID] < Distances[Node] + NeighbourValue:
                Distances[NeighbourID] = Distances[Node] + NeighbourValue
                Previous[NeighbourID] = Node

    print Previous
    Path = []
    Node = Dest
    while not (Node == Source):
        if Path.count(Node) == 0:
            Path.insert(0,Node)
            Node = Previous[Node]
        else:
            break
    Path.insert(0,Source)
    print Path

Answer 1

你的问题是：

if Distances[NeighbourID] < Distances[Node] + NeighbourValue:

将小于号改为大于号，因为您只想用较小的距离替换Neighbor的距离。此外，当您试图找到最小距离时，还必须确保将Distance[i] == -1作为一个单独的案例来处理。你知道吗

固定代码：

 def ShortestPath(self, Source, Dest):
    Distances = {}
    Previous = {}

    for EachNode in self.NodeList.keys():
        Distances[EachNode] = -1
        Previous[EachNode] = ""

    Distances[Source] = 0
    UnseenNodes = self.NodeList.keys()
    while len(UnseenNodes) > 0:
        ShortestDistance = None
        Node = ""
        for TempNode in UnseenNodes:
            if Distances[TempNode] == -1: continue
            if ShortestDistance == None:
                ShortestDistance = Distances[TempNode]
                Node = TempNode
            elif Distances[TempNode] < ShortestDistance:
                ShortestDistance = Distances[TempNode]
                Node = TempNode

        if ShortestDistance is None: break
        UnseenNodes.remove(Node)

        for Neighbour, NeighbourValue in self.NodeList[Node].Connections.items():
            NeighbourID = Neighbour.GetID()
            print NeighbourID
            if Distances[NeighbourID] == -1 or Distances[NeighbourID] > Distances[Node] + NeighbourValue:
                Distances[NeighbourID] = Distances[Node] + NeighbourValue
                Previous[NeighbourID] = Node

    print Previous
    Path = []
    Node = Dest
    while not (Node == Source):
        if Path.count(Node) == 0:
            Path.insert(0,Node)
            Node = Previous[Node]
        else:
            break
    Path.insert(0,Source)
    print Path