Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2000-12-27
2003-05-13
Nguyen, Thu (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
Reexamination Certificate
active
06564145
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a method for finding a shortest path and a computer-readable record media storing instructions for performing the method; and more particularly, to a method for finding a shortest path in a traffic network using a Dijkstra algorithm and a Floyd-warshall algorithm and a computer-readable record media storing instructions for performing the method.
DESCRIPTION OF THE PRIOR ART
A Dijkstra algorithm and a Floyd-warshall algorithm are ones, which are frequently used for finding a shortest path.
The conventional Dijkstra algorithm makes it possible to find a shortest travel time value from a starting node to all other nodes in a network with nonnegative arc values. According to this algorithm, all nodes are classified into two groups of node. One is a permanent node that represents a shortest travel time value from a starting node to a relevant node. The other one is a temporary node that represents an upper bound of a real shortest travel time value from the starting node to the relevant node. Also, a label of a node refers to a shortest travel time value from the starting node along a path whose internal nodes are all permanently labeled. Initially, the starting node is labeled with the permanent node whose travel time value is zero.
According to the Dijkstra algorithm, a node having a minimum temporary label is selected to thereby become the permanent node. The Dijkstra algorithm terminates when all nodes including from the relevant node to neighboring nodes become the permanent node.
The Floyd-warshall algorithm makes it possible to find a shortest path between all pairs of nodes in a network.
According to the Floyd-warshall algorithm, a matrix of &pgr;
ij
is computed. The &pgr;
ij
denotes a travel time value for each of all pairs of nodes, i and j. A &pgr;
ij
(m)
denotes a matrix of a shortest travel time value from the node i and to the node j using 1, 2, . . . , m−1 as the internal node. A &pgr;
ij
(k)
denotes a matrix of a travel time value for each of all pairs of nodes i and j within a starting node and an arrival node. A &pgr;
ij
(k+1)
is computed based on the &pgr;
ij
(k)
. Here, a Triple operation needs to be performed in order to compute the &pgr;
ij
(k+1)
.
FIG. 7
shows one embodiment of a Triple operation according to a Floyd-warshall algorithm.
Here, it is supposed that a &pgr;
ij
(m)
denotes a matrix for a shortest travel time value from the node i and to the node j using 1, 2, . . . , m−1 as an internal node. A &pgr;
ij
(k+1)
is generated by calculating a given &pgr;
ij
(k)
on a following Triple operation.
That is to say, as for a shortest travel time using nodes 1, 2, . . . , k as an internal node, if &pgr;
ij
(k)
<&pgr;
ik
(k)
+&pgr;
kj
(k)
, &pgr;
ij
(k)
=&pgr;
ij
(k+1)
without passing a node k, however if &pgr;
ij
(k)
>&pgr;
ik
(k)
+&pgr;
kj
(k)
, &pgr;
ij
(k)
=&pgr;
ik
(k)
+&pgr;
kj
(k)
with passing the node k.
When representing the above by a mathematical equation, the equation is as follows:
&pgr;
ij
(k+1)
=min {&pgr;
ij
(k)
, &pgr;
ik
(k)
+&pgr;
kj
(k)
}
In other words, a less one of &pgr;
ij
(k)
and &pgr;
ik
(k)
+&pgr;
kj
(k)
is assigned to &pgr;
ij
(k+1)
.
As described above, the conventional Dijkstra algorithm and Floyd-warshall algorithm are used to find a shortest path, however there is a problem that the same node should not be passed twice. Also, there is another problem that the above two algorithm cannot be applied to a real traffic network, in which a Left-turn restriction, a U-turn and a P-turn are included.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a method for finding a shortest path from a starting place to a destination place in a traffic network to thereby reach the destination place in shorter time.
In accordance with an aspect of the present invention, there is provided a method for finding a shortest path from a starting place to a destination place in a traffic network including one or more turn restrictions, one or more U-turns and one or more P-turns using a Dijkstra algorithm, the method including the steps of: assigning a virtual arc connection value from a starting node to a destination node based on traffic information in order to do the turn restriction, the U-turn and the P-turn, wherein the starting node indicates the starting place and the destination node indicates the destination place; selecting a smallest travel time value out of total travel time value for a temporary label node from the starting node to all nodes except for the starting node and assigning the smallest travel time value to a permanent label node; and determining the shortest path by tracing a permanent node stating from the destination node.
REFERENCES:
patent: 5657231 (1997-08-01), Nobe et al.
patent: 5752217 (1998-05-01), Ishizaki et al.
“Dijkstra's Algorithm” from www.cs.usack.ca/resources/tutorials/csconcepts/graphs/tutorial/advanced/dijkstra/dijksrta.html.*
“Dijkstra's algorithm” from www.ece.nwu.edu/~guanghui/Transportation/spt/section3-1.html.*
“Dijkstra's algorithm” from www-comnet.technion.ac.il
etcourse/EE-046335/files/14.pdf.*
“Dijkstra's algorithm for solving the shortest path problem” from www.math.leidenuniv.nl/~monderwa.*
“Method of Finding the Shortest Path on a Road Network with Prohibited Pass”, IBM technical Disclosure Bulletin, vol.41 No.01 Jan. 1998, pp. 721-722.
Jeong Youn-Suk
Kim Hong-Soo
Lee Jong-Hyun
Blakely & Sokoloff, Taylor & Zafman
Korea & Telecom
Nguyen Thu
LandOfFree
Method for finding shortest path to destination in traffic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for finding shortest path to destination in traffic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for finding shortest path to destination in traffic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3023170