Bdtjtk

Been trying to implement Dijkstras algorithm in a user defined graph. But it keeps giving incorrect solutions. Anyway you guys can take a look and help me out?

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

Your problem is in this line:

if Distances[NeighbourID] < Distances[Node] + NeighbourValue:

Change the less-than sign to a greater-than sign, as you only want to replace the Neighbor's distance with a smaller one. Furthermore, you must also make sure that you treat Distance[i] == -1 as a separate case whenever you're trying to find the minimum distance.

The fixed code:

 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