[Olsr-dev] GSoC Incremental Dijkstra

[Yuan Kang]

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.

Thanks,
Jochen
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20110330/3af01196/attachment.html>