Communications in Mathematical Sciences

Volume 14 (2016)

Number 4

A Newton-like algorithm for the shortest path based on the method of evolving junctions

Pages: 1169 – 1180

(Fast Communication)

DOI: http://dx.doi.org/10.4310/CMS.2016.v14.n4.a15

Authors

Shui-Nee Chow (School of Mathematics, Georgia Institute of Technology, Atlanta, Ga., U.S.A.)

Wuchen Li (School of Mathematics, Georgia Institute of Technology, Atlanta, Ga., U.S.A.)

Haomin Zhou (School of Mathematics, Georgia Institute of Technology, Atlanta, Ga., U.S.A.)

Abstract

We present a fast Newton-like algorithm within the framework of the method of evolving junctions (MEJ) to find the shortest path in a cluttered environment. We demonstrate that the new algorithm converges much faster than the existing methods via numerical examples.

Keywords

shortest path problem, Newton method, intermittent diffusions, method of evolving junctions

2010 Mathematics Subject Classification

49J15, 49M15, 60H10

Full Text (PDF format)

Published 6 April 2016