Disjoint Paths

DisjointPaths is a small demo program to demonstrate pathfinding in graphs. The user is provided with a simple user interface which allows him to create an arbitrary graph. After each change to the graph, the program automatically computes the maximal number of edge disjoint paths between the start vertex and the end vertex. Edge disjoint, in this context, means that no edge in the graph can be used by more than one path. Additionally, the paths are computed in such a way that they contain the smallest number of edges possible, i.e. that their overall length is minimized.

The algorithm hence performs a two fold optimization:

  • Maximize the number of edge disjoint paths between start and end
  • Minimize the number of edges used by the paths

The program uses an adapted version of the Ford Fulkerson flow algorithm, in order to compute the minimum cost edge disjoint paths. The algorithm runs in O( n^2 m ) time. For a detailed discussion of the algorithm, see the file Algorithm.pdf, included in the download packages.

Demo Requirements

  • Windows XP or later
  • Usage on Linux and Mac OS requires recompilation

Downloads

Leave a Reply

Your email address will not be published. Required fields are marked *