Самый короткий путь, не возвращающий правильный soluton

Question

Был попыткой реализовать алгоритм Дейкстраса в определенном пользователем графике. Но он продолжает давать неправильные решения. В любом случае, вы, ребята, можете взглянуть и помочь мне?

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 «s с меньшим. Кроме того, вы должны также убедиться, что вы рассматриваете 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