Zusammenfassung

$$d\geq 0$$ d allgemein

$$\mathcal{O}(m+n\cdot\log n) \mathcal{O}(n\cdot m)$$ ASSP

$$\mathcal{O}(m+n\sqrt{\log C})$$

$$\mathcal{O}(n\cdot m+ n^2 \min\{\log n,\sqrt{\log C}\}) \mathcal{O}(n\cdot m+n^2\log n)$$ apsp

$$\mathcal{O}(n^3)^{(*)} \mathcal{O}(n^3)$$

Bemerkung^(*): In der Praxis ist der Floyd-Algorithmus bei kleinen n besser als Dijkstra-Algorithmus.