Shortest Path

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Shortest Path

Mariusz Stanisz
Hi,
 Does anyone have have an implementation or know of a lib of Dijkstra's algorithm.

--

Reply | Threaded
Open this post in threaded view
|

Re: Shortest Path

Geoff Leyland
On 5/05/2010, at 9:51 AM, Mariusz Stanisz wrote:

> Hi,
>  Does anyone have have an implementation or know of a lib of Dijkstra's algorithm.

There's a binary heap here: http://incremental.co.nz/projects/lua.html , which is a good chunk of the work.  I have a few implementations of variations on Dijkstra, A-star and friends buried in a project somewhere, but it doesn't look that easy to extract them.  Can you give more details on the SP problem you want to solve?

Cheers,
Geoff

Reply | Threaded
Open this post in threaded view
|

Re: Shortest Path

Mariusz Stanisz
I just need to find if a path exits between 2 nodes in a mesh network.

On Tue, May 4, 2010 at 5:11 PM, Geoff Leyland <[hidden email]> wrote:
On 5/05/2010, at 9:51 AM, Mariusz Stanisz wrote:

> Hi,
>  Does anyone have have an implementation or know of a lib of Dijkstra's algorithm.

There's a binary heap here: http://incremental.co.nz/projects/lua.html , which is a good chunk of the work.  I have a few implementations of variations on Dijkstra, A-star and friends buried in a project somewhere, but it doesn't look that easy to extract them.  Can you give more details on the SP problem you want to solve?

Cheers,
Geoff




--

Reply | Threaded
Open this post in threaded view
|

Re: Shortest Path

varol kaptan
In reply to this post by Mariusz Stanisz
http://lua-users.org/lists/lua-l/2005-11/msg00218.html

On Tue, May 4, 2010 at 10:51 PM, Mariusz Stanisz
<[hidden email]> wrote:
> Hi,
>  Does anyone have have an implementation or know of a lib of Dijkstra's
> algorithm.
> --
>
>
Reply | Threaded
Open this post in threaded view
|

Re: Shortest Path

Mariusz Stanisz
Thank you

On Tue, May 4, 2010 at 5:37 PM, varol kaptan <[hidden email]> wrote:
http://lua-users.org/lists/lua-l/2005-11/msg00218.html

On Tue, May 4, 2010 at 10:51 PM, Mariusz Stanisz
<[hidden email]> wrote:
> Hi,
>  Does anyone have have an implementation or know of a lib of Dijkstra's
> algorithm.
> --
>
>



--

Reply | Threaded
Open this post in threaded view
|

Re: Shortest Path

Geoff Leyland
In reply to this post by varol kaptan
On 5/05/2010, at 10:37 AM, varol kaptan wrote:

> http://lua-users.org/lists/lua-l/2005-11/msg00218.html
>
> On Tue, May 4, 2010 at 10:51 PM, Mariusz Stanisz
> <[hidden email]> wrote:
>> Hi,
>>  Does anyone have have an implementation or know of a lib of Dijkstra's
>> algorithm.

I'm afraid I don't know what mesh networks are, so I don't know about your application, but if you need your search to be fast, it'd be better to use a heap than the extract_min in that version.

Cheers,
Geoff