Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

TODO: Optimize routing algorithm #68

Open
joemphilips opened this issue Mar 8, 2020 · 0 comments
Open

TODO: Optimize routing algorithm #68

joemphilips opened this issue Mar 8, 2020 · 0 comments
Labels

Comments

@joemphilips
Copy link
Owner

When I ported the routing algorithm from eclair, there were two things I left behind.

  1. 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#.
  2. 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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant