System for determining a route and presenting navigational instructions therefor

A system for determining a route, comprising a computation module adapted to:

• a) receive source location information and use said source location information to identify a source location and a source street associated with said source location;
• b) receive destination location information and use said destination location information to identify a destination location and a destination street associated with said destination location;
• and
• c) execute an algorithm for determining a route between said source location and said destination location, said route comprising a desired solution path;
• wherein:
• i) when at least two of a plurality of possible routes between said source location and said destination location require an identical minimum number of street changes, said algorithm is biased toward determining said route as a shortest route of said at least two of said routes:
• d) wherein said algorithm manipulates a graph representation having a plurality of vertices and a plurality of edges;
• e) each of said edges represents an adjacency between two of said vertices;
• f) said algorithm initially:
• i) designates a source vertex from said vertices, said source vertex representing a beginning street, said beginning street being one of said source street and said destination street,
• ii) designates a destination vertex from said vertices, said destination vertex representing an ending street, said ending street being the other of said source street and said destination street,
• iii) designates said source vertex as seen,
• iv) designates each remaining vertex as unseen, and
• v) places said source vertex in a head position of a first-in-first-out queue;
• g) said algorithm thereafter executes a loop while said destination vertex is designated as unseen and said queue is not empty, in which said algorithm:
• i) when all vertices adjacent to said head-positioned vertex are seen:
• 1) removes said head-positioned vertex from said queue, and
• 2) when a next vertex is next in said queue, places said next vertex in said head position;
• ii) when at least one vertex adjacent to said head-positioned vertex is designated as unseen:
• 1) considers in a consideration order each unseen vertex adjacent to said head-positioned vertex, and
• 2) after all of said unseen vertices adjacent to said head-positioned vertex have been considered:
• a) removes said head-positioned vertex from said queue, and
• b) when a next vertex is next in said queue, places said next vertex
• in said head position;
• h) each of said vertices cannot be simultaneously designated as both seen and unseen;
• and
• i) said consideration order biases said algorithm toward determining said.