[Java] Question regarding the use of a priority queue in algorithms such as dijkstra’s algorithm and finding minimum-cost spanning tree using Prim’s algorithm.
So right now I'm learning about graph algorithms such as single source shortest path and all-pairs shortest path algorithms, as well as algorithms to find the minimum cost spanning tree of a particular graph.
These graphing algorithms sometimes can employ the use of a priority queue to store vertices that need to be visited.
These algorithms set the source to be 0 and every other vertex in the graph to be infinity. Then it will pull the vertex with the minimum cost and update the values of each vertex.
My two questions are:
(1) how do I represent the vertexes in the queue as infinity if they are integers and not doubles?
(2)Also how is it possible to remove something from a queue that isn't in front? For example a vertex in the back of a Queue could have a value of 2 and the vertex in front can have a value of infinity, so you are supposed to remove that smaller vertex first but I thought Queue's only allow first in first out.
Submitted August 31, 2016 at 07:00PM by lyigester
via reddit http://ift.tt/2bDSxnm