g105b / graph Goto Github PK

A connection should not be able to have a negative weight. This will break the algorithm at the moment.

As you're adding all nodes to the queue at the start, not altering their prio on reinserting them, you might want to also implement wikipedia's note about revisiting ("Yet another alternative ... by additionally extracting the associated priority p from the queue and only processing further if p == dist[u]..."). You can set the extraction mode of the php queue to give you the insertion priority as well, so this should be doable.

Investigate the reason the main loop is limited to |N|**2 iterations. Normally finding the end or emptying the queue should be enough, and this extra step is a sign that there might be an issue somewhere.