Algorithm: k shortest paths

[jbarrasa]

For problems like network planning. We need to be able to compute not the shortest but the n shortest paths between two given nodes.

Example: Let's say between nodes A and B there are:

• 2 paths of cost 5
• 3 paths of cost 7
• 10 paths of cost 9

If I call nshortestpaths(A,B,5) I'd get the 5 best i.e. the 2 of cost 5 and the 3 of cost 7.

---

Yens algorithm

https://en.wikipedia.org/wiki/Yen%27s_algorithm

• implement
• procedure
• tests
• edge case tests
• simple benchmark
• benchmark on bigger graphs
• parallelization