Browse Prior Art Database

Method of Finding the Shortest Path on a Road Network with Prohibited Pass

IP.com Disclosure Number: IPCOM000122968D
Original Publication Date: 1998-Jan-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 2 page(s) / 66K

Publishing Venue

IBM

Related People

Hama, T: AUTHOR

Abstract

Disclosed is a program showing the shortest path on a road network with prohibited passing which can be obtained by using a small amount of memory. The shortest path on a road network is conventionally obtained using Dijkstra's shortest path algorithm. However, if, in a road network, there exists a crossing where a specific turn (u-turn, left-turn, or right-turn) is prohibited, a graph expression of road network should be extended so that Dijkstra's algorithm can find the correct shortest path. The new method finds the shortest path by using an additional attribute of an edge of a graph, instead of extending a graph.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 53% of the total text.

Method of Finding the Shortest Path on a Road Network with Prohibited
Pass

      Disclosed is a program showing the shortest path on a road
network with prohibited passing which can be obtained by using a
small amount of memory.  The shortest path on a road network is
conventionally obtained using Dijkstra's shortest path algorithm.
However, if, in a road network, there exists a crossing where a
specific turn (u-turn, left-turn, or right-turn) is prohibited, a
graph expression of road network should be extended so that
Dijkstra's algorithm can find the correct shortest path.  The new
method finds the shortest path by using  an additional attribute of
an edge of a graph, instead of extending a graph.

      A graph is assumed to be directional.  A vertex and an
edge of a graph represent a crossing and a road of a road network,
respectively.  Each edge has a length as an attribute.  As a
preprocessing phase of the method, incoming edges of each vertex are
categorized by their admitted outgoing edges and a unique identifier
(an integer starting from 0) of the category among the incoming edges
is added to an edge as a new attribute (Fig. 1).  The new attribute
is essential to the method of finding the shortest path.  The method
is an extension of Dijkstra's shortest path algorithm.  Utilizing the
new attribute, the method treats a single vertex as several distinct
vertices if it reaches the vertex from incoming edges with different
identifiers.  Thus, the method can work as if a graph were actually
extended.

The method uses the following data structures:
  * Vertex: { id, length, in_edges, out_edges,
        ...