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