Implementation (Part 2)
Leçon 6 sur 9 du cours Algorithme de Dijkstra - Algorithmes de graphes de Coddy.
Maintenant, le calcul glouton du plus court chemin.
Défi
MoyenMaintenant, construisez l'algorithme complet.
Écrivez une fonction nommée dijkstra qui prend n, le tableau plat edges (triplets, dirigés, poids non négatifs), et une source, et renvoie un tableau où la position v est la distance la plus courte de source à v. Utilisez -1 pour les sommets qui ne peuvent pas être atteints.
Commencez toutes les distances à une grande valeur "infinity" sauf la source à 0. Ensuite, n fois, finalisez le sommet non visité le plus proche et relâchez ses arêtes sortantes.
Essayez vous-même
#include <stdlib.h>
int* dijkstra(int n, int* edges, int edges_size, int source, int* returnSize) {
// Écrivez le code ici
*returnSize = 0;
return edges;
}
Testez-vousCette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.
Toutes les leçons de Algorithme de Dijkstra - Algorithmes de graphes
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity