Opened 11 years ago
Last modified 15 months ago
#7676 needs_work enhancement
shortest_path_all pairs in Cython through Floyd Warshall
Reported by: | ncohen | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-wishlist |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Everything is explained there :
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
Change History (11)
comment:1 Changed 11 years ago by
- Status changed from new to needs_work
comment:2 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:3 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:4 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:5 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:6 Changed 2 years ago by
- Milestone changed from sage-6.4 to sage-wishlist
comment:7 Changed 15 months ago by
If nobody else is currently working on this can I go ahead and implement shortest_path_all pair using Floyd warshall algorithm ?
comment:8 Changed 15 months ago by
The first step is to survey the many algorithms we already have with data structures and specific conditions (e.g., weighted, multi edges, loops, etc.).
comment:9 Changed 15 months ago by
I have surveyed all the algorithm and data structure sage has. All pair shortest path works only for an unweighted graph. Although we can use boost interface for this purpose. But I think sage should have its own implementation of Floyd Warshall algorithmhttps://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm for a weighted graph with positive or negative edge weights(but with no negative cycles).
comment:10 Changed 15 months ago by
I don't think sage should have it's own implementation if the one of Boost is fast enough.
You can give it a try, but I'm not sure you can produce something faster than 'Floyd-Warshall_Boost'
.
Note that we already have a (slow) Python implementation 'Floyd-Warshall-Python'
for weighted graphs, and a Cython implementation 'Floyd-Warshall-Cython'
but for unweighted graphs only.
comment:11 Changed 15 months ago by
Thanks for your helpful suggestion. I will look into it.
According to https://ask.sagemath.org/question/44823/sage-floyd-algorithm-in-cython/ SciPy? already includes an implementation of this that is quite fast, and should probably be used over any implementation in Sage.