Grab Bag Release: Shortest Paths

It is done. I’ve completed the rework of my Grab Bag of Useful Stuff, organizing all of my reusable code as a collection of .NET libraries. Feel free to use anything you want, either parts of the source code or the libraries in whole!

Shortest path algorithms were added last, especially the A* might be of use for you.

This week, I’m going to add the API documentation to my website. Additionally, I’ll clean up the code of my Pathfinder tool, a nice Windows Forms application that illustrates the different shortest paths algorithms and serves as showcase for the Grab Bag. This tool will be open-source as well, of course.

Shortest Paths

Let G = (V,E) be an undirected, connected graph with |V| = n vertices and |E| = m edges. We call w: V × V → N the positive edge weight function of G and define w(u,v) = ∞ if (u,v) is not in E. The task is to find the distance d(v) = dist(v,s) from a distinguished source vertex s ∈ V to all other vertices v ∈ V. This classic problem in algorithmic graph theory is called the single-source shortest paths problem.

Finding the shortest path using A*