Implementation (Part 2)
Урок 6 из 9 курса Алгоритм Дейкстры — Алгоритмы на графах на Coddy.
Теперь жадное вычисление кратчайшего пути.
Задание
СреднеТеперь создайте полный алгоритм.
Напишите функцию с именем dijkstra, которая принимает n, плоский массив edges (тройки значений, направленные ребра, неотрицательные веса) и source, и возвращает массив, в котором позиция v — это кратчайшее расстояние от source до v. Используйте -1 для вершин, до которых невозможно добраться.
Установите все начальные расстояния равными большому "infinity", за исключением источника в 0. Затем n раз зафиксируйте ближайшую непосещенную вершину и выполните релаксацию ее исходящих ребер.
Попробуйте сами
#include <stdlib.h>
int* dijkstra(int n, int* edges, int edges_size, int source, int* returnSize) {
// Напишите код здесь
*returnSize = 0;
return edges;
}
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Алгоритм Дейкстры — Алгоритмы на графах
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity