When I ported the routing algorithm from eclair, there were two things I left behind.
- It uses Binary Heap as a data structure to hold the vertex while calculating the route. Original implementation uses Fibonacci Heap, so the time complexity of Dijkstra's algorithm is
O(VlogV * E). But our implementation has O(VlogV * ELogV). (where E and V is the number of edges and vertices). this is because Fibonacci heap is more hard to implement than other more simple Heap type, and I couldn't find reference implementation in F#.
- I didn't care much about converting
ResizeArray -> seq -> list when
finding k-cheapest path by yenKShortestPath . It might improve the performance by not converting intermediate data to other data type.
When I ported the routing algorithm from eclair, there were two things I left behind.
O(VlogV * E). But our implementation hasO(VlogV * ELogV). (where E and V is the number of edges and vertices). this is because Fibonacci heap is more hard to implement than other more simple Heap type, and I couldn't find reference implementation in F#.ResizeArray -> seq -> listwhenfinding k-cheapest path by
yenKShortestPath. It might improve the performance by not converting intermediate data to other data type.