Wprowadzenie

Witamy ponownie w serii Algorytmy grafowe! Do tej pory wszystkie nasze krawędzie były jednakowe. Teraz mają wagę (koszt lub odległość), a my chcemy znaleźć najtańszą trasę.

Algorytm Dijkstry znajduje najkrótsze odległości od pojedynczego źródła do każdego innego wierzchołka w grafie z nieujemnymi wagami krawędzi.

Graf ważony jest dany jako n (wierzchołki od 0 do n - 1) oraz edges, płaska tablica trójek [u0, v0, w0, u1, v1, w1, ...], w której każda trójka oznacza skierowaną krawędź u -> v o wadze w.

Zaczynajmy!