Impressum/Datenschutz
Verschiedene Implementierungen
Für einige Problemklassen existieren zwar exakte Lösungsverfahren, die jedoch sehr viel Rechenzeit in Anspruch nehmen und daher in praktischen Anwendungen nicht zum Einsatz kommen können.

graph solutions bietet für solche Problemklassen daher auch heuristische Verfahren, die gute Näherungslösungen liefern und wesentlich schneller sind.

Einige verfügbaren Implementierungen sind in der gegenüberliegenden Tabelle zusammengestellt.
Function    Algorithms
Shortest Path   
  • Dijkstra für nicht-negative Gewichte
  • FiFo für Gewichte ohne negative Zyklen
Minimum Spanning Tree   
  • Prim
  • Kruskal
Maximum Flow   
  • Ford und Fulkerson
Minimum Cost Flow   
  • Edmonds und Karp
Traveling Salesman   
  • Heuristik: spätere Knotenauswahl wäre schlechter
Chinese Postman   
  • exakt: verzweige und begrenze
  • Heuristik: spätere Kantenauswahl wäre schlechter
  • gierig: nehme die beste verfügbare Kante
Bipartite Matching   
  • exakt: ungarische Methode
  • exakt: Minimalkostenfluß
  • Heuristik: spätere Auswahl der Knotenkombination wäre schlechter
  • gierig: nehme die beste verfügbare Knotenkombination
General Matching   
  • exakt: verzweige und begrenze
  • Heuristik: spätere Auswahl der Knotenkombination wäre schlechter
  • gierig: nehme die beste verfügbare Knotenkombination
Impressum/Datenschutz • Seite geprüft am 27. Sep. 2005