Алгоритм Беллмана — Форда Лабораторная
Need to implement All Pairs Shortest Paths (APSP) Bellman-Ford algorithm on weighted graphs. Create path tracing algorithm for any pair of vertices.
In addition, generate a random graphs based on edge density p and weight w and explain the meaning of your weights.
Generate graph classes for adjacency matrix.
Create path tracing algorithm for any pair of vertices
Compute min distance matrix M from given matrix and shortest path matrix P using Bell-Ford algorithm.
Show the results using any random pair of vertices using cost of edges.
Implement loop invariants and asserts.
______________________________
APSP: All Pairs Shortest Paths due to Bellman-Ford ,
Bellman-Ford Algorithm allows only positive weights.
Floy-Warshal’s Algorithm allows negative weights, but not negative cycles.
Brutforce Approach: repeat Dijkstra’s algorithm on each vertex.
Complexity
O(|V|) ) * O(|E| lg |V|) == O(|V||E|)lg |V|) ),
Since |E| = O(|V|2),
O(|V||E|)lg |V|) ) = O(|V|3)lg |V|) )
Question can we do better than that?
APSP: Bellman-Ford, Floyd-Warshall’s All Pairs Shortest Paths
For both directed and undirected graphs, APSP graph not tree.
For each k, consider the kth row and kth column to fill all other entries.
If the sum (in red) i-row, j-th column is less than the value in (i,j)-th place, replace the entry and record it.
-
2 дня500 UAH
378 85 3 6 2 дня500 UAH
есть реализованый алгоритм Флойда-Уоршела (суть та же, но ищет мин пути между всеми вершинами) на C#, могу отдать или модифицировать под вашу задачу
-
5 дней1000 UAH
726 42 0 1 5 дней1000 UAH
Hi, I think I can try to implement this algorithm on C++ in Qt Creator or Visual studio.
Актуальные фриланс-проекты в категории C и C++
Реверс-инжиниринг консольных утилит для опроса контроллеров SSD (Flash ID)1. Цель работы Выделение программного интерфейса (API) взаимодействия с контроллерами SSD/NVMe из предоставленного набора консольных утилит (Phison, Silicon Motion, Realtek, Maxiotek, Marvell, JMicron и др.). Результатом должно стать рабочий код на языке C/C++ или точная… C и C++, Десктопные приложения ∙ 3 дня 20 часов назад ∙ 5 ставок |
Разработка карты семян Minecraft Java / просмотрщика семян для сайтаРазработка карты семян Minecraft Java / Seed Viewer для сайтаОписание проекта Необходимо разработать браузерный инструмент Minecraft Java Seed Map / Seed Viewer, который будет работать на нашем сайте и позволит пользователю ввести семя Minecraft Java Edition и просмотреть… C и C++, HTML и CSS верстка ∙ 4 дня 3 часа назад ∙ 14 ставок |
Сравнительный анализ эффективности кастомного ПО (v2.2-field) и эталонного ПО (Meshtastic v2.x)
1000 UAH
Сравнительный анализ эффективности кастомного ПО (v2.2-field) и эталонного ПО (Meshtastic v2.x) на идентичной аппаратной платформе (ESP32 + SX1268, 2W) по критериям дальности, пропускной способности, стабильности линка и энергопотребления. Провести тесты с замерами с учетом… C и C++, C# ∙ 8 дней 10 часов назад ∙ 2 ставки |
Консультация и аудит текущего проекта на Odoo 19 Community Edition
Ищем Odoo разработчика — соло-разработчика с опытом разработки на Odoo 19 Community Edition, в том числе с использованием Claude Code. Нам нужен специалист, который успешно реализовал проекты в Odoo и имеет практический опыт разработки с использованием Claude Code. Важно:… C и C++, Javascript и Typescript ∙ 11 дней 11 часов назад ∙ 8 ставок |
Разработка ПО для Arduino (RF-модули 3–7.5 ГГц, автоматическое сканирование частот)Необходимо разработать систему на Arduino для автоматического поиска активного аналогового видеосигнала и автоматической настройки передатчика на обнаруженную частоту.Планируется использование трех отдельных приемно-передающих модулей: 3000–4200 МГц; 4900–6000 МГц; 6100–7500… C и C++, Встраиваемые системы и микроконтроллеры ∙ 12 дней 12 часов назад ∙ 5 ставок |
Chicago