0
ответов
graph - Кратчайший путь с весом вершины
Вот исключение: в некоторых задачах с графами вершины могут иметь веса вместо или в дополнение к весам ребер. Пусть Cv будет стоимостью вершины v, а C(x,y) стоимостью ребра...
вопрос задан: 16 October 2017 00:36
0
ответов
Библиотека Java для хранения и обработки больших (до 600 тыс. вершин) графов
Я работаю над проектом, который будет включать запуск алгоритмов на больших графах. Самые большие два имеют около 300 тыс. и 600 тыс. вершин (я думаю, довольно редко). Я надеюсь найти java-библиотеку, которая сможет...
вопрос задан: 22 September 2017 17:44
0
ответов
Найти кратчайший путь, который проходит через некоторую произвольную последовательность узлов?
В этом более раннем вопросе запросил ОП Как найти кратчайший путь в графе, который идет от U в V, а также проходит через некоторое узкое w. Принятый ответ, который довольно хорош, должен был запустить Dijkstra ...
вопрос задан: 23 May 2017 12:08
0
ответов
Реализация алгоритма Дейкстры с использованием минимальной кучи, но не удалось
Я пытаюсь реализовать алгоритм Дейкстры с использованием минимальной кучи в java, но каждый раз получаю неправильный результат. та же тема на C++. Ниже приведен мой график. Узел A, окрашенный в зеленый цвет, представляет собой ...
вопрос задан: 23 May 2017 12:02
0
ответов
Кратчайший односторонний путь через несколько узлов
У меня есть набор координат графа, и мне нужно найти кратчайший односторонний путь через них все. У меня нет заранее определенного начала / конца, но каждую точку нужно коснуться только один раз и вернуться к ...
вопрос задан: 23 May 2017 11:48
0
ответов
A* манхэттенское расстояние
Я искал алгоритм/псевдокод A* Я следовал ему и закодировал его. Я использовал манхэттенское расстояние для h(n). ( f (n) = g (n) + h (n) )
И вот результат. Это всегда происходит, когда нет стен...
вопрос задан: 8 February 2017 14:35
0
ответов
Алгоритм кратчайшего пути Дейкстры
Ниже приводится краткое изложение алгоритма, данное нам нашим профессором. Что является родителем узла в графе, упомянутом в шаге 3? Я немного сбит с толку, поскольку думал, что узлы имели только ...
вопрос задан: 28 January 2017 16:00
0
ответов
Существует ли реализация двунаправленного поиска для алгоритма Дейкстры? [закрыто]
Я ищу реализацию двунаправленного поиска (он же алгоритм «встречаться посередине») для Дейкстры (или любого другого алгоритма кратчайшего пути от источника к месту назначения) в Java. Как двунаправленный...
вопрос задан: 23 September 2016 02:32
0
ответов
Как работает Breadth-First Search при поиске кратчайшего пути?
Я провел некоторое исследование, и, похоже, мне не хватает одной маленькой части этого алгоритма. Я понимаю, как работает Breadth-First Search, но я не понимаю, как именно он приведет меня к определенному пути, ...
вопрос задан: 5 April 2016 02:42
0
ответов
Ослабляет ли алгоритм Дейкстра края кратчайшего пути в order?
В упражнении 24.3-5 «Введение в алгоритмы, 3-е издание» требуется пример того, что это неверно (не всегда верно). Это возможно? На мой взгляд, это невозможно, потому что каждая грань ослабляется в ...
вопрос задан: 24 April 2015 11:42
0
ответов
Пример кратчайших путей Giraph ClassNotFoundException
Я пытаюсь запустить пример кратчайших путей из инкубатора giraph (https://cwiki.apache.org/confluence/display/GIRAPH/Shortest+Paths+Example). Однако вместо выполнения примера из ...
вопрос задан: 11 March 2015 03:14
0
ответов
Библиотека Javascript для графов (в математическом смысле) [закрыто]
Существуют ли какие-либо важные библиотеки Javascript для графического и сетевого представления с общими алгоритмами, оптимизацией и т. Д.? Я представляю себе что-то вроде лимонной библиотеки C ++, с поиском по графу ...
вопрос задан: 4 December 2014 15:37
0
ответов
Какие структуры данных использовать для алгоритма Дейкстры в Erlang?
Отказ от ответственности: автор является новичком в Erlang. Представьте, что у нас есть граф, состоящий из 1M узлов, и каждый узел имеет 0-4 соседей (ребра исходят от каждого узла к этим соседям, так что ...
вопрос задан: 30 September 2013 18:11
0
ответов
Временная сложность алгоритма Флойда Варшалла
Книга алгоритма Скиены содержит следующее объяснение алгоритма Флойда Варшалла: floyd (adjacency_matrix * g) {int i, j; / * счетчики размеров * / int k; / * промежуточная вершина ...
вопрос задан: 2 July 2013 05:15
0
ответов
Каковы применения алгоритма кратчайшего пути?
Кратчайший путь между узлами в графе может быть найден несколькими алгоритмами (Dikstra, A-star и т. Д.). Но какие приложения у этой проблемы? (Я уже знаю немало, но хотел бы ...
вопрос задан: 8 May 2013 21:22
0
ответов
Отрицательные веса с использованием алгоритма Дейкстры
Я пытаюсь понять, почему алгоритм Дейкстры не работает с отрицательными весами. Читая пример кратчайших путей, я пытаюсь понять следующий сценарий: 2
A ------- B \ /...
вопрос задан: 28 February 2013 17:14
0
ответов
Как переопределить привязку в GIN
Я нахожу ответ на Guice Overriding Binding в Guice, но не знаю, как сделать то же самое для GIN в GWT. Заранее спасибо!
вопрос задан: 15 February 2013 15:48
0
ответов
Насколько водонепроницаем швейцарский сыр? [закрыто]
Представьте себе кусок швейцарского сыра в форме куба -. Моделируем сыр через сетку 20х20х20. Для простоты предположим, что каждый кубик сетки полностью состоит из сыра или полностью из воздуха. На верхнем...
вопрос задан: 1 July 2012 17:37
0
ответов
алгоритм поиска кратчайшего взвешенного пути - часто меняющиеся ребра
Я пытаюсь решить задачу с графом. График взвешенный и неориентированный. Размер графика: нет. вершин до 200 000 шт. ребер до 200 000 Мне нужно найти кратчайший путь между заданными двумя узлами (S &...
вопрос задан: 18 June 2012 06:43
0
ответов
Кратчайший путь в отсутствие данного ребра
Предположим, что нам дан взвешенный граф G(V,E). Граф содержит N вершин (пронумерованных от 0 до N-1) и M двунаправленных ребер. Каждое ребро (vi,vj) имеет положительное расстояние d (т. е. расстояние между ...
вопрос задан: 5 June 2012 10:23
0
ответов
graph - Как найти минимальный направленный цикл (минимальный общий вес)?
Вот исключение: пусть G — взвешенный ориентированный граф с n вершинами и m ребрами, где все ребра имеют положительный вес. Ориентированный цикл — это направленный путь, который начинается и заканчивается в одной и той же вершине...
вопрос задан: 4 May 2012 22:49
0
ответов
Различия между минимальным остовным деревом и деревом кратчайшего пути
Вот акциз :Либо докажите следующее, либо приведите контрпример:(а )Является ли путь между а пара вершин в минимальном остовном дереве неориентированного графа обязательно кратчайшая...
вопрос задан: 4 May 2012 11:56
0
ответов
Поиск кратчайшего пути в графе без каких-либо отрицательных префиксов
Найдите кратчайший путь от источника к месту назначения в ориентированном графе с положительными и отрицательными ребрами, так что ни в одной точке пути сумма ребер, предшествующих ей, не будет отрицательной. Если такого пути нет ...
вопрос задан: 15 March 2012 18:07
0
ответов
Нахождение кратчайшего пути между любыми двумя узлами, принадлежащими двум непересекающимся подмножествам графа.
Существует неориентированный граф, в котором каждому узлу присвоен некоторый цвет. Мне нужно найти кратчайший путь от любого узла синего цвета к любому узлу красного цвета. (В графе могут существовать и другие цвета...
вопрос задан: 15 March 2012 08:35
0
ответов
Как найти кратчайший путь в динамической ситуации
Несколько дней назад, Кто-то спросил меня, Если у нас есть некоторые агенты в нашей среде, и они хотят идти от своих источников к своим пунктам назначения, как мы можем найти общий кратчайший путь для всех из них такой, что ...
вопрос задан: 18 February 2012 16:15
0
ответов
Какой самый простой алгоритм/решение для кратчайшего пути с одной парой через реально взвешенный неориентированный граф?
Мне нужно найти кратчайший путь через неориентированный граф, узлы которого имеют реальные (положительные и отрицательные) веса. Эти веса подобны ресурсам, которые можно получить или потерять, войдя в узел. ...
вопрос задан: 6 January 2012 17:51
0
ответов
Найти оптимизированный путь к расходу через сетку / матрицу в C ++
Я застрял с проблемой и не смог найти много помощи в Интернете. Мне нужно найти минимальную стоимость комбинации чисел из нескольких векторов чисел. Размер вектора же для всех векторов.
Для ...
вопрос задан: 12 September 2011 20:44
0
ответов
Дейкстра против Флойда-Уоршалла: поиск оптимального маршрута для всех пар узлов
Я читал об алгоритме Дейкстры и алгоритме Флойда-Уоршалла. Я понимаю, что Дейкстра находит оптимальный маршрут от одного узла ко всем другим узлам, а Флойд-Уоршалл находит оптимальный ...
вопрос задан: 1 September 2011 19:19
0
ответов
Нахождение k-го кратчайшего пути?
Нахождение кратчайшего пути между двумя точками на графе - это классический вопрос алгоритмов с множеством хороших ответов (алгоритм Дейкстры, Беллмана-Форда и т. Д.) вопрос в том, существует ли эффективный ...
вопрос задан: 27 August 2011 12:06
0
ответов
Проблема маршрута на графике: минимизируйте среднюю стоимость границы вместо общей стоимости
У меня есть взвешенный график, без отрицательных весов, и я хотел бы найти путь от одного узла к другому, пытаясь минимизировать стоимость одного шага. Мне не нужно минимизировать общую стоимость ...
вопрос задан: 25 August 2011 22:25