Értem, most nézem, hogy a te algoritmusod kicsit más, mint amit én úgy 2 éve implementáltam :)
Te az összes csúcsot beteszed a queue-ba előre, de igazából elég a startot, és a tiéd az összes csúcsra megkeresi a legrövidebb utat, nem áll meg a célnál.
Itt nézd meg, Using a priority queue alatt:
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
(és alatta a kiegészítés)
Instead of filling the priority queue with all nodes in the initialization phase, it is also possible to initialize it to contain only source; then, inside the if alt < dist[v] block, the node must be inserted if not already in the queue (instead of performing a decrease_priority operation)
Ezt alkottam C++-ban régebben:
http://pastebin.com/x3m4g7sk
Hiányzik az Edge és a neighbors definíciója, de szerintem kitalálható, hogy mit is csinálnak ezek.