k shortest path problem

[CKerouanton]

Hello, sfnetworks is a great work, thanks!

Would it be possible to integrate a k shortest path function? That would be a great insight for path selection studies in mobility. I think igraph already integrates such a function but I'm not sure.

Thanks

Colin

[luukvdmeer]

The shortest paths functions in sfnetworks are wrappers around igraph functions, so indeed this would depend on if igraph has such a function. As far as I am aware of, they don't.

There is the option in igraph to calculate all simple paths between two nodes. In sfnetworks you can do that by running st_network_paths(from, to, type = "all_simple"). Then, you can afterwards subset that set of all simple paths by selecting only the k shortest ones. However, calculating all simple paths can be terribly slow when you provide a lot of "to" nodes, or when you have a large or very dense network. So it might not be the optimal solution to your problem.

When I am wrong and igraph actually has a function for the k shortest paths routing, of course we should implement an sfnetwork wrapper around that.

[luukvdmeer]

See also: https://github.com/igraph/igraph/issues/1397

[CKerouanton]

hey thanks for your quick reply! Indeed "all simple" can be a very long process, and reducing the network would bring some bias or it would complexify the approach I think... Again thanks, can't wait for the wrapper :)

[idshklein]

did you try to look at the yenpathy package? https://ecohealthalliance.github.io/yenpathy/ it is a bit of a twisted solution but it might work

[CKerouanton]

Hello thanks for the reply, yes I tried it unsuccessfully. I will try again, harder.

[luukvdmeer]

May be coming to the igraph R package soon: https://github.com/igraph/rigraph/issues/972 Once its there we can easily include it in the st_network_paths function

[idshklein]

it's here https://r.igraph.org/reference/k_shortest_paths.html