Is it straightforward to make the Dijkstra's implementation into a secret source to secret destination shortest path?

[jayavanth]

Hello, I was wondering if it's simple to convert the Dijkstra's (all-pairs shortest path) implementation here with secret source node into a secret source to secret destination shortest path. If not, what would I need to do to implement that change?

[mkskeller]

This should be possible as the implementation simply omits producing the index of previous nodes called prev in this pseudo-code: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode The code is already there, just commented out.

[jayavanth]

Thanks @mkskeller! I get how it's done in the pseudocode but I can't seem to find the commented code in the dijkstra function here: https://github.com/data61/MP-SPDZ/blob/b0dc2b36f80822bad73ae40cca70a027bc16d93f/Compiler/dijkstra.py#L225

Is it in some other function?

[mkskeller]

I'm referring to previous created here (and its use later on): https://github.com/data61/MP-SPDZ/blob/b0dc2b36f80822bad73ae40cca70a027bc16d93f/Compiler/dijkstra.py#L233

[jayavanth]

I see, so I just have to uncomment that so I keep track of previous nodes. And in the loop, whenever I see that the previous node is the target node, I stop the search?

[mkskeller]

I don't think that's how it works because the algorithm has to consider all edges to find the shortest path.

[jayavanth]

ok I think I understand now. I wanted to use it for source to destination shortest path in a large graph like a city map. Dijkstra's might not be the best algorithm for this since number of edges are huge. I'll see if related algorithms like bidirectional Dijkstra's or A* is a better fit. I think I can still use this implementation for that as a starting point. Thank you!

[enricobottazzi]

Hi @jayavanth which algorithm did you end up using?