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

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

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

Shortest path not returning correct solution

python

dijkstra

shortest-path

python-2.7