Opened 13 years ago

Closed 13 years ago

## #7540 closed enhancement (duplicate)

# Speed up shortest_path_all_pairs() and update distance_graph

Reported by: | Nathann Cohen | Owned by: | Robert Miller |
---|---|---|---|

Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |

Component: | graph theory | Keywords: | |

Cc: | Rob Beezer | Merged in: | |

Authors: | Reviewers: | ||

Report Upstream: | N/A | Work issues: | |

Branch: | Commit: | ||

Dependencies: | Stopgaps: |

### Description (last modified by )

As mentionned in #7533 by Rob Beezer, the function shortest_path_all_pairs() is much slower than computing independently all the distances, which is a bit worrying. Easy explanation ( at least it is an explanation for me, though there may be a deeper one ), distance() is a function from NetworkX while the Floyd-Marshall algorithm is directly written in Python, hence the slowness.

This function is very fundamental and should be improved ! The difference is amazing :

sage: g=graphs.RandomGNP(200,.1) sage: time e=g.shortest_path_all_pairs() CPU times: user 16.51 s, sys: 0.06 s, total: 16.57 s Wall time: 16.60 s sage: time a=[g.distance(i,j) for (i,j) in Subsets(g,2)] CPU times: user 1.06 s, sys: 0.00 s, total: 1.06 s Wall time: 1.06 s

See http://groups.google.com/group/sage-devel/browse_thread/thread/8edd29e9bddc67e5 for discussion.

### Change History (3)

### comment:1 Changed 13 years ago by

### comment:2 Changed 13 years ago by

Description: | modified (diff) |
---|

### comment:3 Changed 13 years ago by

Milestone: | sage-4.3.1 → sage-duplicate/invalid/wontfix |
---|---|

Resolution: | → duplicate |

Status: | new → closed |

Done in #7966

**Note:**See TracTickets for help on using tickets.

then... use networkx. More precisely,

`networkx.all_pairs_shortest_path`

and`networkx.all_pairs_shortest_path_length`

.They are not based on Floyd-Marshall (it is also in networkx but way slower)