Implementation (Part 2)
Урок 6 из 9 курса Алгоритм Беллмана-Форда — Алгоритмы на графах на Coddy.
Теперь повторяйте проход, пока расстояния не станут окончательными.
Задание
СреднеТеперь полный алгоритм: повторяйте проход релаксации, пока расстояния не стабилизируются.
Напишите функцию с именем bellmanFord, которая принимает n, плоский массив edges (тройки, ориентированные, возможно отрицательные) и source, и возвращает кратчайшее расстояние от source до каждой вершины. Используйте -1 для недостижимых вершин. Предположим, что отрицательных циклов нет.
Выполните релаксацию всех ребер n - 1 раз.
Попробуйте сами
#include <stdlib.h>
int* bellmanFord(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