Timeline for All pairs shortest path with maximum distance
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 28, 2016 at 18:47 | comment | added | Manfred Weis | @StefanKohl it was because of the comments stating it would be inappropriate; but feel free to undelete it. | |
| Feb 28, 2016 at 17:58 | comment | added | Stefan Kohl♦ | Why have you deleted your meta post meta.mathoverflow.net/questions/2768/… , after just half an hour? | |
| Feb 25, 2016 at 9:46 | history | edited | Manfred Weis | CC BY-SA 3.0 |
provided an algorithm for unsorted output of length limited shortest paths
|
| Feb 25, 2016 at 7:43 | comment | added | Manfred Weis | @usul the overhead doesn't come from duplicated work, but rather by evenly growing the shortest path trees according to distance; so the algorithm simulates throwing n stones simultaneously into the water instead to one by one as is ordinarily done when calculating the APSP for sparse graphs by repeated application of the Dijkstra algorithm for each node. | |
| Feb 24, 2016 at 10:29 | comment | added | Manfred Weis | @usul Without further information not much can be said; if you know an upper bound for the shortest path you are interested in and if you know,that the triangle inequality may be violated, then you can filter out all edges that are longer, before actually calculating the paths. It is probably as with sorting: if you have information about the number of inversion you can use a specialized algorithm that will perform poor in the worst case. The same applies to this problem. | |
| Feb 24, 2016 at 8:38 | comment | added | usul | That's an interesting solution but what can we say anything about the performance? I'm worried about duplicating a lot of work. | |
| Feb 24, 2016 at 6:01 | history | answered | Manfred Weis | CC BY-SA 3.0 |