Editorial/Data Protection
Various Implementations
There are algorithms for some classes of problems that calculate exact results, but they need lots of calculation time and are therefore not suited for practical problems that usually can get quite large.

graph solutions offers for such classes of problems heuristic algorithms that yield a good approximation to the exact solution in a much shorter time.

Some available implementations are sumarized in the facing table.

Function    Algorithms
Shortest Path   
  • Dijkstra for nonnegative weights
  • FiFo for weights without negative cycles
Minimum Spanning Tree   
  • Prim
  • Kruskal
Maximum Flow   
  • Ford and Fulkerson
Minimum Cost Flow   
  • Edmonds and Karp
Traveling Salesman   
  • heuristics: later vertex selection would be worse
Chinese Postman   
  • exact: branch and bound
  • heuristics: later edge selection would be worse
  • greedy: take best edge available
Bipartite Matching   
  • exact: Hungarian method
  • exact: minimum cost flow
  • heuristics: later selection of vertex combination would be worse
  • greedy: take best vertex combination available
General Matching   
  • exact: branch and bound
  • heuristics: later edge selection would be worse
  • greedy: take best available
Editorial/Data Protection • page checked on Sep. 27th 2005