Hello All, I need to implement an algorithm, that uses dijkstra's algorithm as key component. However it has two additional requirements on it: 1. If for any two vertices u, v there is an edge and a path of the same length through additional vertices, the direct edge is always selected and 2. If for any two vertices u, v there is more than one shortest path, all calculates shortest path trees that include path u, v contain the same path between those vertices. Now the article that describes the algorithm uses additional property with random values to disambiguate the paths, but I am sure the following two simple rules will achieve the effect more easily: 1. When u is reached at the same distance through two vertices, v and w, the one with lower distance from start will be used in the shortest path tree. 2. When u is reached at the same distance through two vertices, v and w, that both have the same distance from start, the one that comes first in some arbitrary fixed total ordering will be used inthe shortest path tree. These rules are trivially implementable by: 1. Not updating the parent map if the new distance is not strictly less. 2. Using additional criterion in the heap comparing the vertices by index or descriptor if they have the same tentative distance. Now I suspect rule 1 is already satisfied though it's not documented. And if rule 2 is not satisfied, would it be more generally useful and worth, possibly optionally, implementing in the library? -- Jan 'Bulb' Hudec <bulb@ucw.cz>