不返回正确解的最短路径

试图在用户定义的图中实现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

来源

2016-11-26 Thomas O' keeffe

顺便说一句你试图调试它？例如，Pycharm具有很好的python调试器，可以将断点放到每个步骤并进行更多调查。 – pagep

您的问题是在这条线：

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

来源

2016-11-26 18:50:17

是的，那现在就像是一种享受。我不知道你用过的继续声明！谢谢！ –

不返回正确解的最短路径

回答

相关问题