Dijkstra算法python

Question

我试图用Python实现Dijkstra的算法，但是有些东西不起作用。我想在某个地方有个问题，但我找不到。这是我的密码：

def Dijkstra(self, start, end, visited=[], distances = {}, predecessors = {}):
        allV = self.__repo.read_first_line()
        verteces = allV[0]
        if start == end:
        # We build the shortest path and display it
            path=[]
            pred=end
            while pred != None:
                path.append(pred)
                pred=predecessors.get(pred,None)
            path.reverse()
            print('Shortest path: '+str(path)+ " - " + "Cost = "+str(distances[start])) 
        else :     
            if not visited: 
                distances[start]=0
                # visit the neighbors
                neighbours = self.__repo.get_neighbours(start)
                for neighbor in neighbours :
                    if neighbor not in visited:
                        new_distance = distances[start] + self.get_cost(start, neighbor)
                        if new_distance < distances.get(neighbor,float('inf')):
                            distances[neighbor] = new_distance
                            predecessors[neighbor] = start
            # mark as visited
            visited.append(start)
        # now that all neighbors have been visited: recurse                         
        # select the non visited node with lowest distance 'x'
        # run Dijskstra with start='x'
            unvisited={}
            for k in range(1,int(verteces) + 1):
                if k not in visited:
                    unvisited[k] = distances.get(k,float('inf'))  
            x=min(unvisited, key=unvisited.get)
            self.Dijkstra(x,end,visited,distances,predecessors)

Answer 1

实现Dijkstra算法的方法要简单得多。

您可以将其看作是一个BFS，除了：

1. 不是队列，而是使用最小优先级队列.
2. 在找到到达节点的最小成本路径后，我们只考虑节点“访问”。

请参见下面有注释的python实现：

示例输入取自此youtube Dijkstra算法教程

import heapq

graph = {
    'A': {'B': 20, 'D': 80, 'G': 90},
    'B': {'F': 10},
    'F': {'C': 10, 'D': 40},
    'C': {'F': 50, 'D': 10, 'H': 20},
    'D': {'G': 20, 'C': 10},
    'H': {},
    'G': {'A': 20},
    'E': {'B': 50, 'G': 30}
}


def dijkstra(graph, source):
    priority_queue = []
    # The cost is 0, because the distance between source to itself is 0
    heapq.heappush(priority_queue, (0, source))
    visited = {}
    # basically the same as a normal BFS
    while priority_queue:
        # dequeue from the priority queue
        # dequeue the minimum cost path
        (current_distance, current) = heapq.heappop(priority_queue)

        # When we extract min from the priority queue
        # we know that we have found the minimum cost path to this node
        # so we consider it visited
        visited[current] = current_distance

        if current not in graph: continue
        for neighbour, distance in graph[current].items():
            # We only continue to explore neighbours that have been visited
            # (same as a normal BFS)
            if neighbour in visited: continue
            # If we haven't found the min cost path to this node, we push the new distance back onto the queue
            # because this is a min queue, if the new distance is the new min cost path, it will be at the front of the queue
            new_distance = current_distance + distance
            heapq.heappush(priority_queue, (new_distance, neighbour))

    return visited

print dijkstra(graph, 'A')
# {'A': 0, 'C': 40, 'B': 20, 'D': 80, 'G': 90, 'F': 30, 'H': 60}

理想情况下，您可以使用优先级队列字典来降低现有节点的优先级。这将减少内存使用和时间。

但是，一个普通的堆队列会给出同样的正确性，因为如果我们找到一个新的min成本路径，它将被放在队列的前面。

当我们到达成本较高的旧项目时，这些节点就已经被处理了，因此不会影响输出。