Kürzester Pfad

Ein kürzester Pfad ist in der Graphentheorie ein Pfad zwischen zwei unterschiedlichen Knoten $s,t\in V$ eines Graphen, welcher minimale Länge bezüglich einer Kantengewichtsfunktion $c\colon E\to \mathbb {R}$ hat. Haben die Kanten im Graphen alle das Gewicht 1, ist also $c(e)=1$ für alle Kanten $e\in E$ , so ist der kürzeste Pfad ein $s$ – $t$ -Pfad mit der geringstmöglichen Anzahl von Kanten zwischen $s$ und $t$ .

In der Literatur^[1] wird das Problem oft als Shortest Path Problem bezeichnet.

Komplexität

Die Komplexität hängt maßgeblich von der Art der Gewichtsfunktion ab und davon, ob Pfade oder Kantenzüge betrachtet werden. In Kantenzüge können sich Knoten und Kanten wiederholen, während Pfade keinen Knoten doppelt verwenden. Man unterscheidet drei Arten von Gewichtsfunktionen:

Gewichtsfunktionen ohne negative Gewichte;
Konservative Gewichtsfunktion: Eine Gewichtsfunktion heißt konservativ für den Graphen $G$ , wenn $c(C)=\sum _{e\in C}c(e)\geq 0$ für alle Zyklen $C$ von $G$ ;
Gewichtsfunktionen mit beliebigen Gewichten.

Die genaue Problemformulierung ist entscheidend um die Komplexitätsfrage beantworten zu können.

Ohne negative Gewichte: Mit Dijkstras Algorithmus kann man das Problem in einer Laufzeit von $O(m+n\cdot \log(n))$ lösen, wobei $m$ die Anzahl der Kanten und $n$ die Anzahl der Knoten im Graphen bezeichnen. Man beachte, dass die kürzesten Pfade auch kürzeste Kantenzüge sind. Sind alle Gewichte echt positiv, stimmen die kürzesten Pfade mit den kürzesten Kantenzügen überein.
Mit beliebigen Gewichten und mit Kantenzügen: Falls der Graph einen Zyklus enthält, bei dem die Summe über die Gewichte strikt negativ ist, dann gibt es Knoten $s,t$ , die keinen kürzesten Kantenzug haben. Wenn es einen Kantenzug von $s$ zu diesem Zykel gibt und einen Kantenzug von diesem Zykel zu $t$ , dann kann man einen beliebig kurzen Kantenzug von $s$ nach $t$ erzeugen, indem der Zyklus nur hinreichend oft durchlaufen wird. Der Algorithmus von Bellman-Ford kann in einer Laufzeit von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O(nm)} einen kürzesten Kantenzug finden (falls es ihn gibt) oder beweisen, dass es keinen gibt, indem ein negativer Zyklus gefunden wird. Das Entscheidungsproblem, ob es einen Pfad der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \leq C} gibt, lässt sich damit in Polynomialzeit lösen.
Mit beliebigen Gewichten und mit Pfaden: Diese Variante des Problems ist NP-schwer. Dies kann zum Beispiel durch eine Reduktion vom NP-schweren Hamiltonpfadproblem bewiesen werden, indem beim Kürzester-Pfad-Problem alle Gewichte auf −1 gesetzt werden. Man beachtet, dass diese Konstruktion negative Zyklen enthält, und deswegen gilt die NP-Schwere nicht für konservative Gewichtsfunktionen.
Konservative Gewichtsfunktion und mit Pfaden: Der Algorithmus von Bellman-Ford kann in einer Laufzeit von $O(nm)$ einen kürzesten Pfad finden.

Die Literatur beschränkt sich meistens auf nichtnegative Gewichte oder konservative Gewichtsfunktion. Mit einer dieser Zusatzforderungen ist jeder kürzeste Pfad automatisch ein kürzester Kantenzug und deswegen wird in der Literatur diese Unterscheidung oft nicht gemacht.

Im Gegensatz zum Problem des kürzesten Pfades, ist das Problem des längsten Pfades sogar für ungewichtete Graphen NP-schwer.

Variationen des Problems

Abgesehen von der Bestimmung eines kürzesten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} –Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} -Pfades gibt es noch einige weitere, jedoch sehr ähnliche Probleme:

Single-source shortest path (SSSP)

Diese Variante befasst sich mit dem Problem, wie man die kürzesten Wege zwischen einem gegebenen Startknoten und allen übrigen Knoten eines Graphen berechnet. Für nichtnegative Gewichtsfunktionen lassen sich der Dijkstra-Algorithmus bzw. der A*-Algorithmus anpassen, um die kürzesten Wege zu allen Knoten des Graphs zu berechnen. Für beliebige konservative Gewichtsfunktionen berechnet der Bellman-Ford-Algorithmus andererseits stets auch die kürzesten Pfade zu allen anderen Knoten.

Single-destination shortest path (SDSP)

Ziel ist hier die Bestimmung eines kürzesten Pfades zwischen einem Endknoten und allen anderen Knoten des Graphen. Dieses Problem kann durch eine Umkehrung der Kantenrichtungen als SSSP beschrieben werden.

All-pairs shortest path (APSP)

In dieser Variante geht es um die Bestimmung der kürzesten Pfade zwischen allen Knotenpaaren eines Graphen. Abhängig von der Gewichtsfunktion ist es effizienter, für jeden Knoten nacheinander das SSSP lösen oder jedoch spezialisierte Verfahren wie etwa den Floyd-Warshall-Algorithmus oder den Min-Plus-Matrixmultiplikations-Algorithmus zu verwenden, die gleichzeitig für alle Paare kürzeste Pfade bestimmen.

Beispiel

Datei:Prim Algorithm 0.png

Beispielgraph

Im nebenstehend gegebenen Graphen ist ein kürzester Pfad zwischen den Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} der Pfad, welcher in $D$ startet, und über $B$ nach $C$ geht. Die Pfadkosten betragen hierbei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 9+8=17} . Will man jedoch einen Pfad von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D} nach $E$ finden, so ist der direkte Weg mit Kosten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 15} nicht der kürzestmögliche Pfad, da der Weg von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle D} über Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle E} nur Kosten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 14=8+6} hat.

Formulierung als lineares Programm

Zur Bestimmung eines kürzesten Pfades lässt sich außerdem ein lineares Programm heranziehen. Man interpretiert in diesem Fall den Pfad als Fluss mit einem Flusswert von 1 auf den Kanten des Graphen. Die Bestimmung des kürzesten Pfades ist dann ein Spezialfall des Min-cost-flow-Problems. Die entsprechende Formulierung lautet:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} \min & \sum_{e \in E} c_e x_e \\ \text{so dass } & \forall \; v \in V\colon\; \sum_{e \in \operatorname{\delta^-}(v)} x_e - \sum_{e \in \operatorname{\delta^+}(v)} x_e = \begin{cases} -1,& \text{falls } v = s \\ 1,& \text{falls } v = t \\ 0,& \text{sonst } \end{cases} \\ & \forall \; e \in E\colon\; x_e \geq 0 \\ \end{align} }

Falls ein $s$ –Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} -Pfad im gegebenen Graphen existiert, so hat das Programm eine zulässige Lösung. Das Programm ist allerdings unbeschränkt, wenn die Gewichtsfunktion nicht konservativ ist. In diesem Fall kann der Fluss nämlich entlang eines Zykels mit negativen Kosten beliebig weit erhöht werden. Andernfalls hat das Problem eine Optimallösung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} , welche einem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0/1} -Vektor mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |E|} Einträgen entspricht. Die Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{e \in E \,:\, x_e = 1 \}} beschreibt dann einen kürzesten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} –Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} -Pfad, der Zielfunktionswert des Programms entspricht der Länge des Pfades.

Knotenpotentiale

Es stellt sich heraus, dass die Dualisierung des obigen linearen Programms eine anschauliche Interpretation hat. Das duale Programm ist gegeben durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} \max{} & y_t - y_s \\ \text{so dass } & \forall \; e=(u,v) \in E\colon\; y_v - y_u \leq c_e \;\; \end{align} }

Eine Lösung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y} des dualen Programms nennt man ein Knotenpotential. Man sieht leicht, dass für jede Lösung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (y_v)_{v \in V}} der Vektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (y_v + \delta)_{v \in V}} ebenfalls eine Lösung ist, wobei man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \delta \in \mathbb{R}} beliebig wählen kann. Man setzt in der Regel den Wert von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \delta} so, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y_s = 0} . Die Zielfunktion ist dann gegeben durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \max \; y_t} .

Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} ein beliebiger Pfad zwischen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} und einem Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w \neq s} , so lässt sich die Länge des Pfades wie folgt abschätzen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c(P) = \sum_{e \in P} c_e \geq \sum_{e=(u,v) \in P} y_v - y_u = y_w }

Das Potential eines jeden Knotens ist also eine untere Schranke für die Länge eines Pfades. Eine Optimallösung des dualen Programms findet man, wenn man das Potential eines Knotens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w \neq s} als die Länge des kürzesten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} –Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} -Pfades bezüglich der Zielfunktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} setzt.

Anwendungen

Algorithmen, die einen kürzesten Pfad berechnen, finden häufig Anwendung in der Berechnung von Reiserouten. So kann zum Beispiel die Entfernung zwischen zwei Städten berechnet werden. Dabei sind die Städte die Knoten des Graphen und die Straßen die Kanten. Verschiedene Algorithmen sind in der freien Python-Bibliothek NetworkX implementiert.^[2]

Kürzeste Wege mit Nebenbedingungen

Eine Verallgemeinerung des Problems erhält man, wenn man nur Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} –Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} -Pfade Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} betrachtet, die der zusätzlichen Ungleichung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum_{e \in P} u_e \leq U} gehorchen. Dabei ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u \colon E \to \mathbb{R}_+ } eine weitere Gewichtsfunktion und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U} eine reelle Zahl.

Das resultierende Constrained Shortest Path Problem ist dann auch für konservative bzw. nichtnegative Zielfunktionen NP-schwer, siehe H. C. Joksch (1966).^[3]

Literatur

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. 2. Auflage. 2007. ISBN 978-3-486-58262-8
H. C. Joksch (1966). The shortest route problem with constraints. J. Math. Anal. Appl. 14, Seite 191–197

Einzelnachweise

↑ Bernhard Korte, Jens Vygen: Combinatorial Optimization. Theory and Algorithms. 4th edition. Springer, Berlin u. a. 2008, ISBN 978-3-540-71844-4 (Algorithms and Combinatorics 21)
↑ Algorithms - Shortest Paths. In: NetworkX 2.2 documentation. Abgerufen am 24. Oktober 2018 (englisch).
↑ H. C. Joksch (1966)

[1] Bernhard Korte, Jens Vygen: Combinatorial Optimization. Theory and Algorithms. 4th edition. Springer, Berlin u. a. 2008, ISBN 978-3-540-71844-4 (Algorithms and Combinatorics 21)

[2] Algorithms - Shortest Paths. In: NetworkX 2.2 documentation. Abgerufen am 24. Oktober 2018 (englisch).

[3] H. C. Joksch (1966)

[1]

[2]

[3]

Anonym

Suche

Kürzester Pfad

Namensräume

Mehr

Seitenaktionen

Inhaltsverzeichnis

Komplexität

Variationen des Problems

Single-source shortest path (SSSP)

Single-destination shortest path (SDSP)

All-pairs shortest path (APSP)

Beispiel

Formulierung als lineares Programm

Knotenpotentiale

Anwendungen

Kürzeste Wege mit Nebenbedingungen

Literatur

Einzelnachweise

Navigation

Navigation

Mitmachen

Wikiwerkzeuge

Wikiwerkzeuge

Anonym

Suche

Kürzester Pfad

Komplexität

Variationen des Problems

Single-source shortest path (SSSP)

Single-destination shortest path (SDSP)

All-pairs shortest path (APSP)

Beispiel

Formulierung als lineares Programm

Knotenpotentiale

Anwendungen

Kürzeste Wege mit Nebenbedingungen

Literatur

Einzelnachweise

Navigation

Wikiwerkzeuge

Seitenwerkzeuge

Weitere Projekte

Kategorien