"Bug": routing can't find shortest path in every case

[dominicparga]

Maybe the restrictions are used in a wrong way, so not every shortest path could be found. Max comment on this:

The leaving edges depend on the incoming edge, so if a shortest-path would lead through a certain node from a certain edge that enables different outgoing edges than the evaluation of said node before, and such an outgoing edge is only accessible from the incoming edge used at the second evaluation, the algorithm would not provide a correct answer, because the node will not be evaluated two (or more) times.
The correct behaviour could be restored by storing visited nodes in combination with outgoing edges.

[dominicparga]

We agree on accepting this bug for better performance, because we think the problematic situation occurs seldom or never.

[dominicparga]

We should check the performance under following settings: we allow pushing visited nodes into the priority queue.

Possible problems:

• very less performance because too many unused instances are in the queue.
• memory usage in large graphs (e.g. Tokyo, Peking or Baden-Württemberg in South-West-Germany)?

[dominicparga]

I've implemented a data structure providing following functionality:

• It can store objects using a comparator or the objects' natural order. This is implemented using a skip list, because its runtime complexity for all basic operations is in O(logn) (expected with high probability) in contrast to Java's PriorityQueue in O(n) for remove. In addition to get(Object) in O(logn), our skip list implementation provides get(index)in O(logn).
• It can detect duplicates by their hashcodes. If an object with equal hashcode is in the priority queue, the old value is replaced by the new one (with new priority) in O(logn).

With this data structure, the storage is in O(n) with no duplicates where n is equal to the number of nodes. The performance and storage should be checked if object means the tuple (node, incoming edge).

[dominicparga]

Edit to skip list: Access time in comparison to Java's priority queue is doubled, so the skip list is too slow.

[dominicparga]

Possible approximation:
Now, every node is visited once, because the algorithm doesn't terminate with infinite visits per node. We could count the visits and set the bound to 2 or 3 instead of 1.