Dijkstra for k-shortest paths?

YaccConstructor / QuickGraph

Generic Graph Data Structures and Algorithms for .NET

http://yaccconstructor.github.io/QuickGraph/

Microsoft Public License

525 stars 197 forks source link

Dijkstra for k-shortest paths? #195

Open davidlfox opened 5 years ago

davidlfox commented 5 years ago

What's the syntax for using Dijkstra for k-shortest paths e.g. if I want to find the second or third-shortest paths to a vertex by distance?

I thought I was onto something here, but it was just displaying all distances from one vertex.

jnyrup commented 4 years ago

Dijkstra's algorithm will only find the single shortest path. To find the k-shortest paths you can use Yen's algorithm. This library has an implementation of it with a few tests, but according to #178 the are bug(s) in the implementation.

KeRNeLith commented 4 years ago

Hello, I forked this QuickGraph repository (here) and made a fix to the Yen algorithm. Note that I also refactored a lot of the QuickGraph core library in the same time to make it .NET Core compliant.