[Olsr-dev] GSoC Incremental Dijkstra

Henning Rogge (spam-protected)
Wed Mar 30 16:04:11 CEST 2011

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...

"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

More information about the Olsr-dev mailing list