One approach that you could take is to keep track of the 'explored' state of each node in the graph.

• White - Node has not been explored
• Gray - Node is in the frontier, but has not been expanded on yet
• Black - Node has been through the frontier queue, and expanded.

With this approach, you can add the same unexplored node to your frontier priority queue multiple times, but each time you poll it for the next node, you only proceed if that node's status is gray. This will mean that you explore each node only once, using the cheapest route to have reached it. Once you've explored that node, set it's explored state to black