최단 경로가 올바른 soluton을 반환하지 않음

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 

Btw는