Graph.py 文件源码

def shortestPath(self,algo):

        # 1) Assign to each node a tentative distance value (0 for initial, inf for all others)
        # 2) Create a set of visited nodes. Starts with initial node
        # 3) For the current node, consider all of its unvisited neighbors and calulate
        #    (distance to the current node) + (dustance from current node to neighbor)
        #    if this calculated value is less than their tentative value, replace the tentative value with this new value
        # 4) Mark the current node visited
        # 5) if the destination node is marked visited, the search is done
        # 6) set the unvisited node marked with the smallest tentative distance as the next 'current node' and repeat from 3


        if algo == "dijkstra":
            return self.dijkstra_search()

        elif algo == "astar":
            return self.astar_search()

        else:
            print("unknown search algorithm.")