Hi everyone,<br>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.<br>
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?<br>
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.<br>
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.<br>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.<br>
Please contact me if you have any information about the availability of the project, the contact of any mentors, or suggestions about my proposal.<br><br>Thanks,<br>Jochen<br>