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*

Author: npruehs

Nick Pruehs is a Co-Founder of Slash Games, Hamburg. In 2009, he graduated as “Best Bachelor” in computer science at Kiel University. Two years later Nick finished his master’s degree in “Sound, Vision, Games” at Hamburg University of Applied Sciences, becoming the Lead Programmer of Daedalic Entertainment shortly after.

Questions? Comments? Suggestions? Your turn! :)