Introduction

Willkommen zurück zur Graphenalgorithmen-Serie! Bisher waren alle unsere Kanten gleichwertig. Jetzt tragen sie ein Gewicht (Kosten oder eine Entfernung), und wir suchen die günstigste Route.

Dijkstras Algorithmus findet die kürzeste Entfernung von einer einzelnen Quelle zu jedem anderen Knoten in einem Graphen mit nicht-negativen Kantengewichten.

Ein gewichteter Graph ist gegeben als n (Knoten 0 bis n - 1) und edges, ein flaches Array aus Tripeln [u0, v0, w0, u1, v1, w1, ...] wobei jedes Tripel eine gerichtete Kante u -> v mit dem Gewicht w ist.

Fangen wir an!