Описание тега dijkstra
Алгоритм Дейкстры, разработанный голландским ученым-компьютерщиком Эдсгером Дейкстрой, представляет собой алгоритм поиска по графу, который решает проблему кратчайшего пути с одним источником для связного графа с неотрицательными краевыми издержками пути, создавая дерево кратчайших путей. Этот алгоритм часто используется в маршрутизации и как подпрограмма в других алгоритмах графа.
1
ответ
boost::dijkstra_shortest_paths перезаписывает вес внутреннего графа?
Я использую Boost Graph Library для хранения неориентированного графа с double граничные веса и double веса вершин. В нескольких местах моего кода мне нужно применить алгоритм Дейкстры для поиска кратчайших путей. Это работало довольно хорошо, пока …
12 сен '12 в 07:39
2
ответа
Python - Расчет расстояния в Дейкстре
У меня возникли проблемы с определением расстояния каждого узла от начального узла, а точнее с получением какой-либо информации обратно. Я не получаю вывод из своей функции, прикрепленной по следующей ссылке. #Values to assign to each node class Nod…
09 мар '11 в 22:35
1
ответ
Откуда происходит это исключение NullPointerException?
for(Node<T> neighbor : current.getAdjacentNodes()) { neighbor.setDistance(current.getDistance() + neighbor.getDistance()); queue.add(neighbor); } Я получаю исключение NullPointerException из этого цикла for. Я действительно не знаю, как этого …
28 июн '14 в 11:34
1
ответ
Создание неориентированного графа с правильными краями
Здравствуйте, я создаю 100 графиков для тестирования в алгоритме Дейкстры. У меня есть проверка, чтобы убедиться, что два случайно сгенерированных номера узла для соединения не совпадают. Однако я не понимаю, как проверить, существует ли пара, чтобы…
21 дек '15 в 04:40
3
ответа
Как мне начать делать лабиринт с кратчайшим путем из матрицы лабиринта в Java?
Поэтому я хотел бы создать лабиринт с кратчайшим путем, который решает лабиринт. Лабиринт похож на это: Мои лабиринты всегда будут окружены стеной. Кроме того, @ это стены, если вы не можете сказать. @@@@@@@@ @ S@ @ @@@ @@E@ @ @ @ @@@ @@ @@@@@@@@ Гд…
24 июл '11 в 21:07
5
ответов
Кратчайший путь между необработанными географическими координатами и узлом графика
Я реализовал простой алгоритм Дейкстры для нахождения кратчайшего пути на карте.osm с Java. Поиск пути в графе, который создается из файла.osm, работает довольно хорошо. Но если текущее местоположение и / или пункт назначения пользователя не являетс…
12 апр '11 в 10:03
2
ответа
Ошибка присваивания нулевого указателя.
Ниже приведен код алгоритма кратчайшего пути Дейкстры. Код прекрасно работает на небольших входах, но мне нужно его для 2d размера массива 200. Поэтому я использовал динамическое распределение памяти. Тем не менее, это дает ошибку присваивания нулев…
20 июл '12 в 17:20
2
ответа
Почему алгоритм Дейкстры использует ключ уменьшения?
Алгоритм Дейкстры научили меня такому while pqueue is not empty: distance, node = pqueue.delete_min() if node has been visited: continue else: mark node as visited if node == target: break for each neighbor of node: pqueue.insert(distance + distance…
13 фев '12 в 04:29
0
ответов
Neo4j: кратчайший путь между известным начальным узлом и несколькими конечными узлами
У меня есть график с ~10000 узлов, я пытаюсь найти самый длинный путь между известным начальным узлом и неизвестным конечным узлом, но с Reader известного типа. Когда у меня было 1000 узлов, это вычислялось нормально за 4 секунды, но теперь это зани…
05 фев '18 в 16:25
1
ответ
Не уверен с алгоритмом Дейкстры
С помощью многих людей на этом сайте у меня есть замечательный код. К сожалению, алгоритм Дейкстры не работает. Предполагается найти кратчайшее расстояние между ИИ и игроком и приблизить ИИ к игроку. Я не знаю, как заставить это вернуть путь и как п…
17 янв '18 в 19:50
2
ответа
Как алгоритм кратчайшего пути Дейкстры работает с приоритетными очередями?
Я читал веб-сайты в Интернете, и все говорят, что использование очереди с приоритетами принесет пользу, но я не понимаю, что здесь используется в качестве "приоритета". В самом начале, является ли первый элемент в очереди приоритетов всегда узлом на…
05 ноя '15 в 03:31
0
ответов
Реализация алгоритма Дейкстры в Java?
Поэтому я пытаюсь реализовать алгоритм Дейкстры в Java. Я знаю, что есть разные способы сделать это, но вот способ, которым я научился это делать. Поэтому я начинаю с одной вершины и нахожу кратчайший путь от этой вершины ко всем остальным вершинам.…
29 ноя '16 в 16:42
2
ответа
График минимального веса пути
У меня есть взвешенный график. Я хочу найти лучший путь от узла S к узлу E, чтобы максимальный вес одного ребра, который был внутри этого пути, был наименьшим из возможных. Например: S -> E (w=40) S -> A (w=30) A -> E (w=20) Для этого графа…
13 июл '16 в 15:03
1
ответ
dijkstra_shortest_paths Boost Graph Lib 1.57.0 не работает
Я использую BGL и недавно перешел на 1.57.0 с 1.46.1. Я также переключился с использования Xcode на Mac на gcc 4.9.2. Я получаю несоответствующий вызов функции, чтобы получить и создал этот небольшой фрагмент кода, чтобы проиллюстрировать проблему. …
20 дек '14 в 03:41
1
ответ
Реализация алгоритма Дейкстры с использованием очереди приоритетов
Я реализую Алгоритм Дейкстры, используя приоритетную очередь, я хочу, чтобы функция удаляла элемент из кучи, но я могу только послать ему индекс вершины из главного Дейкстры, и я не могу найти его позицию в куче, и я не могу позволить себе сделать б…
21 янв '14 в 09:46
0
ответов
Решить с помощью графика кратчайшего пути для значений best[u]?
Я нашел решение, но я не понимаю, откуда взялась 1, которая добавляет лучшее (u) и присваивает лучшее (V). while Q is not empty do u ← vertex in Q with smallest dist[] for all edges (u, v) ∈ E do if dist(v)>dist(u)+l(u, v) then dist(v)← dist(u)+…
24 сен '17 в 17:42
1
ответ
Как реализовать параллельный алгоритм Дейкстры с использованием OpenMP/MPI
Я пытаюсь реализовать параллельную версию алгоритма Дейкстры (мой самый первый параллельный алгоритм) для курсового проекта. Я без проблем выполнил последовательную часть, используя приоритетную очередь, но у меня возникли проблемы с поиском способа…
01 июн '13 в 20:17
3
ответа
Как получить минимальный элемент из приоритетной очереди после изменения содержимого очереди
Я пытался реализовать алгоритм Дейкстры, используя priority queue в Java.. К сожалению, он возвращал неправильные результаты... Я разыскал проблему. Вот проблема. После вставки весов узлов в очередь, я изменяю вес этих узлов, но когда я пытаюсь удал…
14 июн '15 в 05:25
1
ответ
Алгоритм поиска пути
Я пытаюсь разработать приложение, которое отображает мой офис (точно так же, как приложение, например, карты Google, показывающее путь от одного места к другому). Из того, что я читал до сих пор, для решения проблемы могут использоваться алгоритмы, …
12 май '15 в 17:16
0
ответов
Сложные свойства отношений в базе данных Neo4j
Я разрабатываю планировщик маршрутов на Neo4j для образовательных целей. Я разработал некоторый алгоритм по этому поводу, и я использую как запрос шифрования, так и Rest API в своем проекте. Но есть проблема, которая не устранена мной. Я пытаюсь выч…
23 июн '14 в 18:34