A binary heap is a complete binary tree that is ordered such that, for any given vertex, all of the vertex’s children have lower priority than it.ĭijkstra’s algorithm solves the single-source shortest path problem. Priority queues are commonly implemented as binary heaps, and that is how I implemented my priority queue. A stack is a priority queue where elements have more precedence the later they enter the container. A queue is a priority queue where elements have more precedence the earlier they enter the container. You can actually think of stacks and queues as types of priority queues. The item that has the highest priority is the item that gets removed. In Dijkstra’s algorithm, the data structure is a priority queue. The last item that you put into it is the first item that you remove from it. In depth-first search, the data structure is a stack. The first item that you put into it is the first item that you remove from it. In breadth-first search, the data structure is a queue. One of the many interesting things that I learned from my artificial intelligence class is that the big difference between breadth-first search, depth-first search, and Dijkstra’s algorithm is the data structure that stores the vertices.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |