Implementacja (część 2)

Lekcja 6 z 9 w kursie Algorytm Dijkstry — algorytmy grafowe w Coddy.

Teraz zachłanne obliczanie najkrótszej ścieżki.

Wyzwanie

Średni

Teraz zbuduj pełny algorytm.

Napisz funkcję o nazwie dijkstra, która przyjmuje n, płaską tablicę edges (trójki, skierowane, nieujemne wagi) oraz source i zwraca tablicę, w której pozycja v zawiera najkrótszą odległość od source do v. Dla wierzchołków, do których nie można dotrzeć, użyj -1.

Ustaw wszystkie odległości na dużą wartość „nieskończoności”, z wyjątkiem źródła, dla którego ustaw 0. Następnie, n razy, ostatecznie wybierz najbliższy nieodwiedzony wierzchołek i zrelaksuj jego krawędzie wychodzące.

Spróbuj swoich sił

#include <stdlib.h>

int* dijkstra(int n, int* edges, int edges_size, int source, int* returnSize) {
    // Napisz kod tutaj
    *returnSize = 0;
    return edges;
}