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 |
| | |
|
| Maximum Flow |
| | |
|
| Minimum Cost Flow |
| | |
|
| 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
|
