Timeline for Finding all shortest paths between two vertices
Current License: CC BY-SA 3.0
25 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 19, 2015 at 16:04 | answer | added | Juho | timeline score: 9 | |
| Oct 27, 2013 at 22:02 | comment | added | rjkaplan | My apologies! I have just accepted one of the solutions. I forgot to do so. | |
| Oct 27, 2013 at 22:01 | vote | accept | rjkaplan | ||
| Oct 27, 2013 at 19:13 | comment | added | Alex | @rjkaplan as you haven't accepted the answers would you please tell me how you solve the problem?Did you code it separately? | |
| Apr 15, 2012 at 18:58 | comment | added | DavidC | @rjkaplan I updated my shortest path solution with a directional graph. | |
| Apr 12, 2012 at 3:09 | history | edited | rm -rf♦ | CC BY-SA 3.0 |
deleted 52 characters in body; edited title
|
| Apr 12, 2012 at 3:02 | answer | added | DavidC | timeline score: 19 | |
| Apr 11, 2012 at 15:37 | history | edited | rjkaplan | CC BY-SA 3.0 |
Added a detail about the problem
|
| Apr 11, 2012 at 15:35 | comment | added | rjkaplan | @SimonWoods Thanks for the response! But irrespective of memory usage, that method would work only for unweighted graphs. | |
| Apr 11, 2012 at 13:57 | answer | added | Heike | timeline score: 16 | |
| Apr 11, 2012 at 13:56 | comment | added | Szabolcs | @SimonWoods That's worth posting as an answer despite the high memory usage. It shouldn't be lost in the comment jungle. | |
| Apr 11, 2012 at 12:39 | answer | added | Dr. belisarius | timeline score: 12 | |
| Apr 11, 2012 at 9:57 | comment | added | PlatoManiac |
@SimonWoods The example with BreadthFirstScan works for very small toy problems but even for GridGraph with dimension $12 \times 14$ memory consumption increases with out bound.
|
|
| Apr 11, 2012 at 9:43 | comment | added | celtschk | Thinking about it, to get the union of shortest paths you probably don't need the set of shortest paths. I think the following algorithm should give you the union: Step 1: For each node, calculate the graph distance both to the start vertex A and the destination vertex B (let's call those values the A-distance and B-distance of that vertex). Step 2: Remove all edges whose weight is not both the difference between the A-distances of the vertices it connects and the difference between the B-distances. If I'm not wrong, the resulting graph should be exactly the union of all shortest paths. | |
| Apr 11, 2012 at 9:31 | comment | added | Simon Woods |
The documentation for BreadthFirstScan has an example of this problem under Examples-Applications-Shortest Path Applications.
|
|
| Apr 11, 2012 at 9:28 | comment | added | celtschk |
@ruebenko: The problem is of course that of the question: Finding all shortest paths between two vertices of a given graph. Do you possibly think of enumerating all possible non-intersecting paths (an exponentially growing set!) and using Nearest to select those with length equal to GraphDistance? I don't think that would give a solution in acceptable time for moderately complex graphs. Anyway, the question already contains all information needed to define the problem. Indeed, even the first sentence of my comment already does, and so does the title of the question.
|
|
| Apr 11, 2012 at 9:11 | history | tweeted | twitter.com/#!/StackMma/status/190004258530279424 | ||
| Apr 11, 2012 at 9:09 | comment | added | user21 |
@celtschk, that depends on the problem, but something like this: Nearest[{1, 2, 4, 8, 16, 32}, 20, All]. You can specify a metric and/or create a NearestFunction. But all this needs more information in the question - an example would help.
|
|
| Apr 11, 2012 at 9:09 | comment | added | PlatoManiac | There is similar question stackoverflow.com/questions/2819347/… . The third answer is not a bad idea. | |
| Apr 11, 2012 at 9:01 | comment | added | celtschk |
@ruebenko: How would you apply Nearest to this problem?
|
|
| Apr 11, 2012 at 9:00 | comment | added | celtschk | A brute-force way to do it would be to break the path found by removing one of the edges of the shortest path, calculating the shortest path again, and if it has the same length, it's another shortest path of the original graph. You would have to do that for each edge of the shortest path, as well as recursively (i.e. for the newly found shortest path remove further edges; however here it should be sufficient to remove edges which are not also part of the original shortest path). | |
| Apr 11, 2012 at 8:56 | comment | added | user21 |
Have you considered Nearest?
|
|
| Apr 11, 2012 at 7:22 | comment | added | Szabolcs | This is a good question. The system must have at least some internal implementation for use in calculating the betweenness centrality, but I can't seem to find a user-accessible function. | |
| Apr 11, 2012 at 7:17 | history | edited | Szabolcs | CC BY-SA 3.0 |
added 4 characters in body
|
| Apr 11, 2012 at 7:08 | history | asked | rjkaplan | CC BY-SA 3.0 |