\( \newcommand{\dist}{\textnormal{dist}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\pfrac}[2]{\left(\frac{#1}{#2}\right)} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \)

7. Graphen mit Kantenkosten

In Kapitel 6.2 haben wir die Breitensuche kennengelernt, einen Algorithmus, der uns in einem Graphen \(G= (V,E)\) ausgehend von einem Knoten \(s\) die kürzesten Pfade zu jedem anderen Knoten \(v\) findet. Dies funktioniert allerdings nur, wenn alle Kanten "gleich teuer" sind. In Wirklichkeit haben wir häufig Graphen mit Kantenkosten. Wir wollen dann zum Beispiel nicht unbedingt den Pfad mit den wenigsten Kanten, sondern den mit den geringsten Gesamtkosten.