[jgrapht-users] Fwd: [ jgrapht-Patches-3163001 ] LevitShortestPath

[John S. <js...@gm...>]

Hi folks,

Via email, I got a contribution of a new shortest-path algorithm.  I
don't have a lot of background on its provenance, so for now I'm
uploading it to the patch system.  If someone (in particular someone
with Russian-language skills) wants to do some more research on it and
help get it ready for submission, that would be great.

Thanks,
JVS

---------- Forwarded message ----------
From: SourceForge.net <no...@so...>
Date: Thu, Jan 20, 2011 at 2:00 PM
Subject: [ jgrapht-Patches-3163001 ] LevitShortestPath
To: no...@so...


Patches item #3163001, was opened at 2011-01-20 14:00
Message generated for change (Tracker Item Submitted) made by perfecthash
You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=579689&aid=3163001&group_id=86459

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: None
Group: None
Status: Open
Priority: 5
Private: No
Submitted By: John V Sichi (perfecthash)
Assigned to: Nobody/Anonymous (nobody)
Summary: LevitShortestPath

Initial Comment:
Submitted by Oleg A. Morozov via email, with a link to this reference
in Russian:

http://rain.ifmo.ru/cat/view.php/vis/graph-paths/levit-2002/algorithm

Like Dijkstra, assumes non-negative edge weights.

Needs some work before commit:

* reformat code and review data structures used
* add unit tests (at a minimum, reuse some of the existing shortest path tests)
* get some more background on the algorithm's computation complexity
and use cases for which it is best-suited



----------------------------------------------------------------------

You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=579689&aid=3163001&group_id=86459