Описание тега bellman-ford
The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph. For graphs with only non-negative edge weights, the faster Dijkstra's algorithm also solves the problem. Thus, Bellman–Ford is used primarily for graphs with negative edge weights. The algorithm is named after its developers, Richard Bellman and Lester Ford, Jr.
1
ответ
Алгоритм Беллмана-Форда для объяснения отрицательных циклов
Я попытался реализовать алгоритм BF для обнаружения отрицательного цикла. Я следовал лекционным заметкам, чтобы реализовать алгоритм. Мое решение было следующее: def belman_ford(s, adj, cost): arr_len = len(adj) dist_arr = [MAX_VAL]*arr_len prev_arr…
28 дек '18 в 05:03
0
ответов
Беллман Форд для ориентированного графа G находит кратчайшие пути за одну итерацию
Для данного ориентированного графа G вершина s и все v∈V(G) находятся на расстоянии 1 ребра от вершины s. Можно ли найти конкретный порядок ребер (из E(G)) так, чтобы одна итерация прохождения Беллмана Форда по этим ребрам в этом порядке находила вс…
03 мар '18 в 18:55
1
ответ
Ограничения на алгоритмы Дейкстры, Беллмана и топологического алгоритма кратчайшего пути?
Какие точные ограничения / условия существуют, чтобы можно было использовать любой из этих трех алгоритмов SPT на графах для вычисления кратчайших путей?
05 фев '15 в 08:18
0
ответов
Какие условия для обновления таблицы в алгоритме DVR?
Я читал алгоритм DVR из TCP/IP Protocol Suite от Бехруза А. Форузана. Здесь я прочитал, что если входящая запись скажет R от какого-либо маршрутизатора, скажем A, то к таблице маршрутизатора скажем, что C отсутствует в таблице C, поэтому она обновит…
16 ноя '17 в 09:43
1
ответ
Как дать входные данные из файла в C++?
У меня есть исходный код на C++ для алгоритма Беллмана Форда. Он получает входной файл с узлами, ребрами, исходным узлом и узлом назначения и возвращает кратчайший путь от одного узла к другому. Тип файла: 30 150 29 30 //Vertices,Nodes,SourceNode,De…
06 июн '15 в 17:22
1
ответ
Нахождение всех вершин на отрицательных циклах
Я знаю, что проблема проверки того, принадлежит ли данное ребро взвешенного орграфа отрицательному циклу, является NP-полной ( нахождение минимального подграфа, содержащего все отрицательные циклы), и Беллман-Форд позволяет проверять вершину на то ж…
23 май '13 в 17:52
2
ответа
Беллман Форд обнаруживает отрицательный цикл самой короткой длины
Решение этой проблемы Арбитража UVA http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid;=8&page;=show_problem&problem;=40 но я застрял в поиске отрицательного цикла наименьшей длины (длина здесь - число вершин). Вот мой код, который у…
18 окт '14 в 11:21
1
ответ
Параллельная реализация Bellman-Ford
Может ли кто-нибудь указать мне хороший псевдокод простого параллельного алгоритма кратчайшего пути? Или любой язык, это не имеет значения. У меня проблемы с поиском хороших примеров =[
17 ноя '13 в 16:15
1
ответ
Почему эта реализация Bellman-Ford не работает?
Следующий пример содержит отрицательный цикл, и все же программа, похоже, не находит его. Может кто-то указать, что не так? Предполагается распечатать отрицательный цикл, если он существует, но программа не делает то, что ожидается. #include <ios…
13 апр '13 в 03:02
1
ответ
Количество самых легких путей из вершины с одним источником
Предположим, у меня есть ориентированный взвешенный граф с положительными или отрицательными весами (без нулевых или отрицательных взвешенных циклов). Граф анализируется Беллманом-Фордом, то есть каждая вершина содержит данные о самом легком пути к …
12 май '15 в 20:08
1
ответ
Кратчайший путь в взвешенном ориентированном графе
Мне нужно найти кратчайший путь между двумя узлами s,t во взвешенном ориентированном графе. Вот ограничения: Вес может быть отрицательным. Путь должен пройти через конкретное ребро, давайте назовем ее e и shes от узла u к v. Выходной путь должен быт…
10 янв '19 в 20:20
1
ответ
Почему бы не ослабить все ребра в первой итерации алгоритма Беллмана Форда?
Пожалуйста, обратитесь к следующей странице для алгоритма Беллмана Форда (он показывает, например). http://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm Я до сих пор не понимаю. В первой итерации внешнего цикл…
21 ноя '11 в 16:34
2
ответа
Прав ли я относительно различий между алгоритмами Флойд-Варшалла, Дейкстры и Беллмана-Форда?
Я изучал эти три, и я излагаю свои выводы из них ниже. Может ли кто-нибудь сказать мне, достаточно ли я их понял, или нет? Спасибо. Алгоритм Дейкстры используется только тогда, когда у вас есть один источник, и вы хотите знать наименьший путь от одн…
28 июл '12 в 21:03
1
ответ
Беллман-Форд: все кратчайшие пути
Я успешно реализовал Bellman-Ford, чтобы найти расстояние по кратчайшему пути, когда ребра имеют отрицательные веса / расстояния. Я не смог заставить его возвращать все кратчайшие пути (когда есть связи для кратчайших). Мне удалось получить все крат…
06 июл '12 в 21:24
1
ответ
Большая O Обозначение Алгоритма, составленного из меньших алгоритмов
Я работаю над заданием, которое берет некоторый граф, добавляет к нему дополнительную вершину, применяет Беллмана Форда с новой вершиной в качестве источника, а затем использует все пары Дейкстры на графе. Используемые алгоритмы имеют требования вре…
25 фев '14 в 17:27
1
ответ
Реализация Bellman-Ford в Python
Я пытаюсь адаптировать алгоритм графа Беллмана-Форда в Python к своим потребностям. Я разработал часть анализа из файла JSON. Вот код Bellman Ford, который я нашел на github: https://github.com/rosshochwert/arbitrage/blob/master/arbitrage.py И вот м…
27 дек '17 в 16:57
1
ответ
Решите, все ли кратчайшие пути от s до t содержат границы
Пусть G = (V;E) - ориентированный граф, все ребра которого имеют неотрицательные веса. Пусть s, t 2 вершины в V, и пусть e ребро в E. Опишите алгоритм, который решает, все ли кратчайшие пути из s в t содержат ребро e. Итак, вот как вы можете достичь…
04 мар '13 в 00:29
1
ответ
Найти минимальные максимальные веса в взвешенном графике с помощью динамического программирования
Я ищу алгоритм, который находит путь из двух вершин, скажем, от s до t , в графе, который имеет ровно k ребер, если пути существуют. И если было найдено несколько путей, предпочтителен маршрут с минимальными максимальными весами одного ребра. (не об…
06 окт '11 в 14:21
1
ответ
Самый быстрый алгоритм для определения наличия отрицательного цикла на графике
Я использую матрицу d представить график. d.(i).(j) означает расстояние между i а также j; v обозначает количество узлов в графе. Возможно, что в этом графике есть отрицательный цикл. Я хотел бы проверить, существует ли отрицательный цикл. Я написал…
03 июн '13 в 13:52
1
ответ
Вариация алгоритмов Беллмана-Форда?
У нас есть Направленный граф с 100 вершинами. v1 -> v2 -> ... v100 и веса всех ребер равны 1. Мы хотим использовать Bellman-ford для нахождения всех кратчайших путей от v1 до других вершин. Этот алгоритм на каждом этапе проверяет все ребра в произво…
20 фев '16 в 16:49