3
$\begingroup$

I know that you can calculate the shortest path in a vectorized fashion using Floyd-Warshall, e.g. like proposed by Han and Kang, however I want the matrix, they call "via", the actual route taken through the graph.

Is it possible to retrieve this "via" matrix from a similar vectorized algorithm?

Actually I do not need all-pairs shortest path, but have two nodes, that I just wish to calculate the distance between, however I want to do it vectorized. I cannot seem to find algorithms, that allow me to get the actual path, and not just the distance, when doing it vectorized.

Is it at all possible?

$\endgroup$
  • 1
    $\begingroup$ Can't you use the normal way to also compute paths during floyd warshall? en.wikipedia.org/wiki/… $\endgroup$ – adrianN May 26 '16 at 12:55
  • $\begingroup$ What exact restrictions do you tie to the term "vectorized"? One can, for instance, parallelize Bellman-Ford on shared-memory architectures but I'm not sure the algorithm I have in mind counts as "vectorized". $\endgroup$ – Raphael May 26 '16 at 13:43
  • $\begingroup$ @Raphael With vectorized I mean "can be done with vector algebra", so that it indeed can be parallelized. Implementation-wise I want to do it with "pure" NumPy. Essentially I want to substitute the nested for-loops with matrix multiplication. $\endgroup$ – Mads Ohm Larsen May 27 '16 at 6:52
  • $\begingroup$ @adrianN The "normal way" of Floyd-Warshall isn't vectorized, but three nested for-loops, so while it solves my problem of getting the "via"-matrix, it doesn't scale. With the vectorized way that Han and Kang suggests I do not get the "via"-matrix, but the computation for the shortest path is vectorized. I want a mix between the two. $\endgroup$ – Mads Ohm Larsen May 27 '16 at 6:53
  • 1
    $\begingroup$ If I read the paper correctly, they eventually call FWI, that contains the same if statement as the normal algorithm. I think you could add the path computation there, like in the normal algorithm. BTW, have you seen this? I think you should update your question with why you need this. If it's for speedup only, I think you'll have a hard time beating Dijkstra. $\endgroup$ – adrianN May 27 '16 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.