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*

Grab Bag Release: Minimum Spanning Trees

Okay, the last weeks have been full of work, my apologies for the delay. This weekend, I finally managed to finish my implementation of the algorithm for finding minimum spanning trees by Fredman and Tarjan, here we go.

Minimum Spanning Trees

Let G = (V, E) be a connected, undirected graph with |V| = n vertices and |E| = m edges (v, w) with non-negative edge weights c(v, w). A minimum spanning tree of G is a spanning tree of G with minimum total edge weight.

Minimum Spanning Tree

The algorithm presented in “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms” by Michael L. Fredman and Robert Endre Tarjan in 1985 finds a minimum spanning tree of an input graph in O(m ß(m,n)), where

ß(m,n) = min{ i | log(i) n ≤ (m/n)}

and log(i) n is defined inductively by

  • log(0) n = n
  • log(i + 1) n = log log(i) n