search

MatejSloboda / Dijkstra_map_for_Godot

MIT License
77 stars 13 forks source link

Documentation coverage #78

Closed arnaudgolfouse closed 3 years ago

arnaudgolfouse commented 3 years ago

This is (mostly) a change in documentation.

The main improvement is the use of the new (1.48) linking method of rustdoc.

MatejSloboda commented 3 years ago

Removing the id field from QueuePriority breaks some behavior of the algorithm. The id is a tie-breaker when multiple paths have the same cost. It guarantees that a graph with the same points (with identical point ids), connections and weights produces the same shortest paths. Without this, the shortest paths map may depend on order in which the connections were created, because Hashsets that store neighboring points do not guarantee consistent iteration order.

This determinism is rarely something you care about in practice... until you do...

arnaudgolfouse commented 3 years ago

Removing the id field from QueuePriority breaks some behavior of the algorithm. The id is a tie-breaker when multiple paths have the same cost. It guarantees that a graph with the same points (with identical point ids), connections and weights produces the same shortest paths. Without this, the shortest paths map may depend on order in which the connections were created, because Hashsets that store neighboring points do not guarantee consistent iteration order.

This determinism is rarely something you care about in practice... until you do...

Ah I see... Do you want me to revert it ?