Browse Prior Art Database

Method for Searching Shortest Path between Dynamic Two Nodes

IP.com Disclosure Number: IPCOM000123727D
Original Publication Date: 1999-Apr-01
Included in the Prior Art Database: 2005-Apr-05
Document File: 1 page(s) / 21K

Publishing Venue

IBM

Related People

Shibuya, T: AUTHOR

Abstract

Disclosed is a method for searching shortest path between a dynamic source and a dynamic destination on directed graph with no negative edges like road networks, ATM networks, and so on. Our method enables very fast recomputation of shortest paths.

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

Method for Searching Shortest Path between Dynamic Two Nodes

   Disclosed is a method for searching shortest path between
a dynamic source and a dynamic destination on directed graph with no
negative edges like road networks, ATM networks, and so on.  Our
method enables very fast recomputation of shortest paths.

   Let  G=(V,E)   be the graph to be used.  Our method uses a
shortest path tree from the temporary destination  t memberof G.  Let
p(v) be the shortest path length from a node v to t that can be
obtained by the tree.  In our method, we use h(v) = max{p(v)-p(u),
h'(v,u)} as an  A sup * estimator (1) for recomputing any shortest
path to u, where h'(v,u) is 0 or some other A sup * estimator for u
such as the Euclidean distance on road networks.
  Reference
  (1) N. J. Nilsson, Problem-Solving Methods in Artificial
      Intelligence, McGraw-Hill, New York, 1971.