Implementation (Part 2)
Lección 6 de 9 del curso Algoritmo de Dijkstra - Algoritmos de grafos de Coddy.
Ahora el cálculo voraz del camino más corto.
Desafío
IntermedioAhora construye el algoritmo completo.
Escribe una función llamada dijkstra que reciba n, el arreglo plano edges (triples, dirigidos, pesos no negativos) y un source, y devuelva un arreglo donde la posición v sea la distancia más corta desde source hasta v. Usa -1 para los vértices que no se puedan alcanzar.
Comienza todas las distancias en un "infinity" grande excepto el source en 0. Luego, n veces, finaliza el vértice no visitado más cercano y relaja sus aristas salientes.
Pruébalo tú mismo
#include <stdlib.h>
int* dijkstra(int n, int* edges, int edges_size, int source, int* returnSize) {
// Escribe el código aquí
*returnSize = 0;
return edges;
}
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
Todas las lecciones de Algoritmo de Dijkstra - Algoritmos de grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity