Kürzeste Wegeproblem

Einfache Sprache

Ist mit dem Erreichbarkeitsproblem in Graphen verwand.

Kürzeste Wegeproblem

Gegeben ein gewichteter,Gerichteter Graph $G=(V,E)$ mit $V=\{0,\ldots,n\}$, $E\subseteq\{(i,j)|1\leq i\not=j\leq n\}$ und eine Vervollständigte Entfernungsmatrix $A$. Gesucht: Bestimme für jedes $j\in V$ die Länge $u_j$ eines kürzesten Weges ohne Knotenwiederholungen von $1$ nach $j$. D.h. die kleinste Weglänge $w(p)=\sum_{i=0}^{k-1}a_{v_iv_{i+1}}$ über alle Wege $P=[v_0,\ldots,v_k]$ mit $v_0=1$ und $v_k=j$.

Lösungen

• Algorithmus von Dijkstra
• Algorithmus von Bellman und Ford
• A*-Algorithmus