shortest_path should be faster

[GoogleCodeExporter]

pygraph.algorithms,minmax.shortest_path executes in n^2 time, as indicated by a 
comment in the function. A modified version using a priority queue with a 
binary insert is n*log(n). I've attached a diff against r708 as well as the 
complete function for easy inspection.

Thanks

Original issue reported on code.google.com by peter.sagerson@gmail.com on 24 Jul 2010 at 2:34

Attachments:

• shortest_path.diff
• shortest_path.py

[GoogleCodeExporter]

Have you re-run this against the test-suite?

Original comment by salimfadhley@gmail.com on 24 Jul 2010 at 8:17

[GoogleCodeExporter]

Of course. The tests pass with the change. Outstanding test suite, by the way.

Original comment by peter.sagerson@gmail.com on 24 Jul 2010 at 3:49

[GoogleCodeExporter]

One other thing to note: if you call the current implementation with an invalid 
source (a node that is not in the graph), it will return ({source: None}, 
{source: 0}). This is probably a bad choice, as it is indistinguishable from 
the case where source is a valid node with no neighbors. It's also arguably 
inconsistent with the documentation: "Inaccessible target nodes do not appear 
in either dictionary." The proposed implementation will raise a KeyError in 
this case, which I think is a legitimate response. My second choice would be 
returning ({}, {}).

Since this edge case is neither documented nor tested, one could argue that 
it's undefined behavior and not necessarily subject to backwards compatibility. 
However, the old behavior could be emulated if this is a concern.

Original comment by peter.sagerson@gmail.com on 24 Jul 2010 at 5:08

[GoogleCodeExporter]

Original comment by pmatiello on 3 Oct 2010 at 8:25

• Changed state: Accepted

[GoogleCodeExporter]

Original comment by pmatiello on 3 Oct 2010 at 8:46

• Changed state: Started

[GoogleCodeExporter]

Merged in r720.

Original comment by pmatiello on 3 Oct 2010 at 9:14

• Added labels: Type-Enhancement
• Removed labels: Type-Defect

[GoogleCodeExporter]

Original comment by pmatiello on 3 Oct 2010 at 9:14

• Changed state: Fixed