1/10/2024 0 Comments Python priority queue algorithm"""Visit all nodes and calculate the shortest paths to each from start""" You could re-write your function (with better variable names) to: def dijkstra(graph, start): The point is that you visit the shorter path to a given node before the longer path, and you don't need to alter the heapq items in-place to achieve that. Just keep a set of visited nodes so you know to skip any longer paths. You only need to push nodes onto the heap that you reached, really you'll end up with multiple entries for some of the nodes (reached by multiple paths), but the heapq will still present the shortest path to that node first. To use the heapq correctly, you need to put the edge length first, and you don't alter the values on the heap if you use tuples you can't accidentally do this. Because the heapq is not used correctly, you always traverse the nodes in alphabetical order. In your code that's the node name, not the distance, and the heapq order of items is never updated when the distances in the list items are altered. The heap is sorted by first by the first value in the list items you pushed in. The reason you don't see any difference is because the implementation of the algorithm is actually broken, as the heap is not used correctly. When you assign directly to pq_update, you remove that connection. The pq heap has a reference to the same list object, so changes to pq_update will also be visible in entries still to be processed on heap! Note that the entry list is also shared wit the heapq. You want to update the distance, not replace the list, so pq_update is used. So pq_update is a list with both the vertex and the distance. The pq_update dictionary contains lists, each with two entries: for vertex, value in ems(): Note: the implementation you have is broken and doesn't correctly implement Dijkstra. Instead of writing pq_update (which is how I did it), it does not seem to change anything so why is it included ?ĭistances = , I would like to understand in the following WORKING AND FINISHED code, why when updating pq_update, it is written as pq_update.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |