Graphentheorie: Unterschied zwischen den Versionen
| [gesichtete Version] | [Markierung ausstehend] |
K (Hob den Schutz von „Graphentheorie“ auf) |
|||
| Zeile 7: | Zeile 7: | ||
# [[Transportproblem]] | # [[Transportproblem]] | ||
# [[Zuordnungsproblem]] | # [[Zuordnungsproblem]] | ||
| + | |||
| + | |||
| + | Möchte man für einen gewählten Startpunkt den kürzesten Weg oder kleinsten Baum (d.h. kürzester Weg von Startknoten zu jedem Knoten im Graph) errechnen, | ||
| + | so verwendet man dazu den Dijkstra Algorithmus. | ||
| + | |||
| + | Sollen für jede Kombination von Start- und Zielknoten der kürzeste Weg errechnet werden, verwendet man den Floyd-Algorithmus. | ||
| + | (Dies lässt sich auch mit dem Dijkstra errechnen, indem man über sämtliche Knoten iteriert und in jeder Iteration den kleinsten Baum errechnet. Der Flyod-Algorithmus erfordert hierfür aber deutlich weniger Berechnungschritte) | ||
Version vom 26. Oktober 2012, 18:32 Uhr
In diesem Teil geht es um das Thema Graphentheorie. Dazu zählt zunächst die Definition von Graphen und deren Unterscheidung, um kürzeste Wege, um maximale Flußmengen und auch die Anwendungsgebiete, in denen sich Graphen einsetzen lassen.
- Grundlagen zur Graphentheorie
- Dijkstra Algorithmus
- Floyd Algorithmus
- Maximaler Fluss, Ford Fulkerson
- Transportproblem
- Zuordnungsproblem
Möchte man für einen gewählten Startpunkt den kürzesten Weg oder kleinsten Baum (d.h. kürzester Weg von Startknoten zu jedem Knoten im Graph) errechnen,
so verwendet man dazu den Dijkstra Algorithmus.
Sollen für jede Kombination von Start- und Zielknoten der kürzeste Weg errechnet werden, verwendet man den Floyd-Algorithmus. (Dies lässt sich auch mit dem Dijkstra errechnen, indem man über sämtliche Knoten iteriert und in jeder Iteration den kleinsten Baum errechnet. Der Flyod-Algorithmus erfordert hierfür aber deutlich weniger Berechnungschritte)
