Алгоритм Беллмана - Форда

@denisglod · Регистрация: 22.12.2014

Author24 — интернет-сервис помощи студентам

Подскажите, я вроде бы посчитал правильно но конечный результат в таблице я так и не понял. Какой же все таки кратчайший путь из точки S в точку D.

@salam · 27.08.2017, 19:56

ну все правильно, 2.

@denisglod · 27.08.2017, 20:29 **[ТС]**

Сообщение от salam

ну все правильно, 2.

можете пожалуйста объяснить что значит цифра 2, это кол-во ребер или что?
PS объясните на "пальцах".

@SupremeEP · 31.08.2017, 23:30

У тебя в таблице [v][k] ([строка][столбец]) обозначает кратчайший путь из вершины S в вершину v, содержащий $https://www.cyberforum.ru/cgi-bin/latex.cgi?\leq k$ рёбер.

Добавлено через 15 минут
Динамика: $https://www.cyberforum.ru/cgi-bin/latex.cgi?[u][k] = min([u][k - 1], [v][k - 1] + w_v)$

Доказательство. Мы будем рассматривать кратчайшие пути длиной k рёбер. Допустим ребро весом w, исходящие из вершины v, идёт в вершину u. Тогда кратчайший путь в вершину u будет либо тот, который был в [u][k - 1], либо путь проходящий через вершину v в u, то есть [v][k - 1] + w. Так как в циклах мы пройдём по всем вершинам и рёбрам, мы можем заключить, что таким образом мы найдём самые кратчайшие пути, которые будут лежать в [v][E], где E - количество рёбер в графе. □

Новые блоги и статьи Все статьи Все блоги /
Интеграция Hangfire с RabbitMQ в проектах C#.NET stackOverflow 18.04.2025 Разработка современных . NET-приложений часто требует выполнения задач "за кулисами". Это может быть отправка email-уведомлений, генерация отчётов, обработка загруженных файлов или синхронизация. . .	Построение эффективных запросов в микросервисной архитектуре: Стратегии и практики ArchitectMsa 18.04.2025 Микросервисная архитектура принесла с собой много преимуществ — возможность независимого масштабирования сервисов, технологическую гибкость и четкое разграничение ответственности. Но как часто бывает. . .	Префабы в Unity: Использование, хранение, управление GameUnited 18.04.2025 Префабы — один из краеугольных элементов разработки игр в Unity, представляющий собой шаблоны объектов, которые можно многократно использовать в различных сценах. Они позволяют создавать составные. . .	RabbitMQ как шина данных в интеграционных решениях на C# (с MassTransit) stackOverflow 18.04.2025 Современный бизнес опирается на множество специализированных программных систем, каждая из которых заточена под решение конкретных задач. CRM управляет отношениями с клиентами, ERP контролирует. . .	Типы в TypeScript run.dev 18.04.2025 TypeScript представляет собой мощное расширение JavaScript, которое добавляет статическую типизацию в этот динамический язык. В JavaScript, где переменная может свободно менять тип в процессе. . .
Погружение в Kafka: Концепции и примеры на C# с ASP.NET Core stackOverflow 18.04.2025 Apache Kafka изменила подход к обработке данных в распределенных системах. Эта платформа потоковой передачи данных выходит далеко за рамки обычной шины сообщений, предлагая мощные возможности,. . .	Коммуникация в реальном времени с SignalR в C# на примере создания чата UnmanagedCoder 17.04.2025 Современный веб стремительно эволюционирует от статичных страниц к динамичным приложениям, где пользователи ожидают мгновенной реакции на свои действия. Представим, что вы отправляете сообщение. . .	Реализация CQRS с MediatR на C# .NET stackOverflow 17.04.2025 Современная разработка программного обеспечения постоянно ищет пути повышения эффективности организации кода. Архитектурные паттерны появляются, эволюционируют, и те, что проявляют свою. . .	Verilog и интеллектуальная собственность - "глазами" обученной LM модели. Hrethgir 17.04.2025 В сети встречаются участники, заявляющие что код на Verilog ни о чём не говорит. Но вот патентная практика на самом деле показывает обратное ими утверждаемому. То-есть код на Verilog включают в. . .	Свап-файл дополнительно к разделу (если вдруг не хватает или не создан) jigi33 17.04.2025 ПОДКЛЮЧЕНИЕ ДОПОЛНИТЕЛЬНОГО SWAP ПРОСТРАНСТВА, Т. О. , РАСШИРЕНИЕ ЕГО РАЗМЕРА В Linux можно использовать как раздел подкачки (swap), так и файл подкачки (swap-файл). Чтобы создать swap-файл вместо. . .

@denisglod 1 / 1 / 4 Регистрация: 22.12.2014 Сообщений: 46

	Алгоритм Беллмана - Форда 27.08.2017, 18:03. Показов 1133. Ответов 3 Метки алгоритм, БеллманаФорда (Все метки) Подскажите, я вроде бы посчитал правильно но конечный результат в таблице я так и не понял. Какой же все таки кратчайший путь из точки S в точку D. Миниатюры 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	27.08.2017, 19:56
	ну все правильно, 2. 0

@denisglod 1 / 1 / 4 Регистрация: 22.12.2014 Сообщений: 46
	27.08.2017, 20:29 [ТС]
	Сообщение от salam ну все правильно, 2. можете пожалуйста объяснить что значит цифра 2, это кол-во ребер или что? PS объясните на "пальцах". 0

@SupremeEP 4 / 4 / 2 Регистрация: 01.12.2015 Сообщений: 36
	31.08.2017, 23:30
	У тебя в таблице [v][k] ([строка][столбец]) обозначает кратчайший путь из вершины S в вершину v, содержащий $https://www.cyberforum.ru/cgi-bin/latex.cgi?\leq k$ рёбер. Добавлено через 15 минут Динамика: $https://www.cyberforum.ru/cgi-bin/latex.cgi?[u][k] = min([u][k - 1], [v][k - 1] + w_v)$ Доказательство. Мы будем рассматривать кратчайшие пути длиной k рёбер. Допустим ребро весом w, исходящие из вершины v, идёт в вершину u. Тогда кратчайший путь в вершину u будет либо тот, который был в [u][k - 1], либо путь проходящий через вершину v в u, то есть [v][k - 1] + w. Так как в циклах мы пройдём по всем вершинам и рёбрам, мы можем заключить, что таким образом мы найдём самые кратчайшие пути, которые будут лежать в [v][E], где E - количество рёбер в графе. □ 0

Опции темы