Implementation (Part 2)
Lição 6 de 9 do curso Algoritmo de Dijkstra - Algoritmos de Grafos da Coddy.
Agora, o cálculo ganancioso do caminho mais curto.
Desafio
MédioAgora construa o algoritmo completo.
Escreva uma função chamada dijkstra que receba n, o array plano edges (triplas, direcionadas, pesos não negativos) e um source, e retorne um array onde a posição v seja a distância mais curta de source até v. Use -1 para vértices que não podem ser alcançados.
Inicie todas as distâncias com um "infinito" grande, exceto a origem (source) em 0. Então, n vezes, finalize o vértice não visitado mais próximo e relaxe suas arestas de saída.
Experimente você mesmo
#include <stdlib.h>
int* dijkstra(int n, int* edges, int edges_size, int source, int* returnSize) {
// Escreva o código aqui
*returnSize = 0;
return edges;
}
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Algoritmo de Dijkstra - Algoritmos de Grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity