Opened 11 years ago

# shortest_path_all pairs in Cython through Floyd Warshall

Reported by: Owned by: ncohen rlm major sage-wishlist graph theory N/A

### Description

Everything is explained there :

### comment:1 Changed 11 years ago by ncohen

• Status changed from new to needs_work

### comment:2 Changed 8 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

### comment:3 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:4 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:5 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:6 Changed 2 years ago by embray

• Milestone changed from sage-6.4 to sage-wishlist

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.

### comment:7 Changed 15 months ago by gh-vipul79321

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 dcoudert

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 gh-vipul79321

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 dcoudert

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 gh-vipul79321

Thanks for your helpful suggestion. I will look into it.

Note: See TracTickets for help on using tickets.