K Shortest Paths Algorithm for NetworkX
2,035 views
Skip to first unread message
Greg Bernstein
Apr 4, 2015, 2:53:14 PM4/4/15
to networkx...@googlegroups.com
Is there interest in incorporating a K shortest (loop less) paths algorithm into NetworkX? A while ago, for teaching and R&D purposes, I implemented a version of Yen's K-shortest path algorithm in Python/NetworkX. The code has been posted with the rest of the code for a (data/optical) network course at http://grotto-networking.com/netDesignCourse.html#Code with Sphinx generated documentation at http://grotto-networking.com/files/NetDesignCourse/code_doc/Utilities.html#module-Utilities.YenKShortestPaths.
I've included the two relevant files. I recently heard from a biophysics PhD student that has used this code on networks with several thousand nodes and links to find hundreds of shortest paths.
If there is sufficient interest I can try to modify these to meet NetworkX coding/style/API standards.
Thanks to the developers/contributors of NetworkX for a great library.
Greg B.
Dr. Greg M. Bernstein
P.S. The modified Dijkstra code also works with an algorithm for link disjoint paths if there is any interest in that...
I've included the two relevant files. I recently heard from a biophysics PhD student that has used this code on networks with several thousand nodes and links to find hundreds of shortest paths.
If there is sufficient interest I can try to modify these to meet NetworkX coding/style/API standards.
Thanks to the developers/contributors of NetworkX for a great library.
Greg B.
Dr. Greg M. Bernstein
P.S. The modified Dijkstra code also works with an algorithm for link disjoint paths if there is any interest in that...
Aric Hagberg
Apr 4, 2015, 3:00:18 PM4/4/15
to networkx...@googlegroups.com
Hi,
Yes, we are definitely interested in k-shortest path and edge disjoint
paths algorithms. I think the relevant open issue at our Github site
is
https://github.com/networkx/networkx/issues/793
Are you a github user? If you open or add to an issue there the
developers will see it and comment.
Thanks!
Aric
> --
> You received this message because you are subscribed to the Google Groups
> "networkx-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to networkx-discu...@googlegroups.com.
> To post to this group, send email to networkx...@googlegroups.com.
> Visit this group at http://groups.google.com/group/networkx-discuss.
> For more options, visit https://groups.google.com/d/optout.
Yes, we are definitely interested in k-shortest path and edge disjoint
paths algorithms. I think the relevant open issue at our Github site
is
https://github.com/networkx/networkx/issues/793
Are you a github user? If you open or add to an issue there the
developers will see it and comment.
Thanks!
Aric
> You received this message because you are subscribed to the Google Groups
> "networkx-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to networkx-discu...@googlegroups.com.
> To post to this group, send email to networkx...@googlegroups.com.
> Visit this group at http://groups.google.com/group/networkx-discuss.
> For more options, visit https://groups.google.com/d/optout.
Greg Bernstein
Apr 5, 2015, 11:57:34 AM4/5/15
to networkx...@googlegroups.com
Great. I'm a github user, but not terribly experienced. I'll check against the open issue you mention and post concerning both algorithms.
Cheers
Greg
Cheers
Greg
Poria Hajian
Mar 4, 2016, 12:46:43 PM3/4/16
to networkx-discuss
hi,
thanks for the program
do you have any solved network with this program?
i don't know how to implement the program because i have no idea how can i introduce the network to program.
thanks in advance
thanks for the program
do you have any solved network with this program?
i don't know how to implement the program because i have no idea how can i introduce the network to program.
thanks in advance
Reply all
Reply to author
Forward
0 new messages