不返回正確解的最短路徑

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