[Olsr-dev] Dijikstra

[L. Aaron Kaplan]

On Mar 29, 2010, at 7:01 PM, Airton Ishimori wrote:

> Hi list,
> 
> The olsrd-0.5.6-r8 utilize the Dijikstra algorithm for calculate better path? The Shortest Path Algorithm implemented into olsrd-0.5.6-r8 is the same that the Dijikstra or not? If not, which is the difference?

Mainly more efficient datastructures and faster algorithms (complexity wise).

Here are some notes from the OLSR-NG Dijkstra optimization steps:

http://wiki.funkfeuer.at/index.php/OLSR-NG
http://wiki.funkfeuer.at/index.php/Data_Structures_and_Algorithms

This shows the asymptotic complexity of different Dijkstra implementations:

http://wiki.funkfeuer.at/index.php/Datei:O-Dijkstra.gif
http://wiki.funkfeuer.at/index.php/SPF_refactoring

Hope it helps,
a.