[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: [Help-glpk] big mod-file ... big problem
From: |
Michael Hennebry |
Subject: |
RE: [Help-glpk] big mod-file ... big problem |
Date: |
Thu, 28 Jun 2007 15:51:51 -0500 (CDT) |
On Thu, 28 Jun 2007, pacho wrote:
> There are like 180 thousands of nodes in the net :-)
> Best solution for me, is to have it counted before www timeout :-)
If you also have 10 billion arcs, 51 minutes isn't all that bad.
For a single shortest path problem, there are O(m + n log(n)) alogrithms,
where m and n are the number of arcs and nodes, respectively.
They assume random access memory.
It might also be useful to realize that if path P is a shortest
path from A to Z, any subpath of P is also a shortest path.
--
Mike address@hidden
"Horse guts never lie." -- Cherek Bear-Shoulders