[Olsr-dev] GSoC Incremental Dijkstra

[Henning Rogge]

On Wed, Mar 30, 2011 at 15:32, Yuan Kang <(spam-protected)> wrote:
> Hi everyone,
> I am Jochen Kang, and I am a third-year Computer Science student at Columbia
> University. I am very interested in both networks and graph algorithms. I
> have taken, and am taking, classes in computer networks, learning about
> network programming (in C), protocols and administration, and have also
> taken courses in algorithms and data structures in general, and graph theory
> in particular.
> So when I looked through the ideas in Freifunk's wiki, I was very interested
> in the incremental dijkstra project. However, I was told on the Freifunk
> list that the ideas were from last year. I looked through the olsr_spf.c
> code and it appears that it still only implemented the traditional form of
> Dijkstra's algorithm. Is that project still open, and is there a mentor for
> that?
> My idea is to have each node also contain a tree of nodes for which it is
> the second-to-last hop, as well as the node's own second-to-last node from
> the source, which would need its list changed if the path changed.
> When an edge increases its weight (or disappears), we only need to
> recalculate for the nodes whose paths included the old edge, which we can
> search from the further node on the edge.
> When an edge decreases its weight, we decrement the cost of paths that use
> that edge, but the paths stay the same otherwise, since they were already
> optimal without the cost decrease. Then we only recalculate for points
> further than the further node of the changed edge. I am still considering
> more ways to narrow down the nodes that need to be recalculated, but am not
> certain about their correctness.
> Please contact me if you have any information about the availability of the
> project, the contact of any mentors, or suggestions about my proposal.
Please look at the "incremental" branch... and ask Markus about whats
going on there...

Henning
-- 
"Wo kämen wir hin, wenn alle sagten, wo kämem wir hin, und niemand
ginge, um einmal zu schauen, wohin man käme, wenn man ginge." (Kurt
Marti)