Вопросы по теме 'dijkstra'

Могу ли я использовать алгоритм Прима вместо алгоритма Дейкстры для поиска кратчайшего пути?
Я весь день боролся за понимание алгоритма Дейкстры и его реализацию без каких-либо значительных результатов. У меня есть матрица городов и их расстояний. Что я хочу сделать, так это указать точку отправления и точку назначения, чтобы найти...
2957 просмотров
shortest-path dijkstra prims-algorithm minimum-spanning-tree
schedule 28.02.2023
Какой самый простой алгоритм / решение для кратчайшего пути одной пары через неориентированный граф с реальными весами?
Мне нужно найти кратчайший путь через неориентированный граф, узлы которого являются действительными (положительными и отрицательными) взвешенными. Эти веса подобны ресурсам, которые вы можете получить или потерять, войдя в узел. Общая стоимость...
2791 просмотров
java algorithm shortest-path dijkstra floyd-warshall
schedule 12.05.2022
Модификация алгоритма Дейкстры для реализации A*
Я нахожусь в процессе создания имитации лабиринта мыши, бегущей по лабиринту. Алгоритм Дейкстры великолепен и все такое, но он не особенно влияет, когда участвуют кошки, поэтому я пытаюсь изменить мою существующую реализацию Дейкстры на поиск A * с...
540 просмотров
c a-star dijkstra graph-algorithm implementation
schedule 08.03.2023
Алгоритм Дейкстры против поиска по единообразной стоимости (временная сложность)
У меня следующий вопрос: согласно разным источникам, алгоритм Дейкстры - это не что иное, как вариант поиска по унифицированной стоимости. Мы знаем, что алгоритм Дейкстры находит кратчайший путь между источником и всеми пунктами назначения...
3301 просмотров
dijkstra ucs
schedule 02.05.2022
Как реализовать алгоритм Дейкстры на Прологе, возвращающий список ребер?
Я уже некоторое время пытаюсь реализовать алгоритм кратчайшего пути Дейкстры в JIProlog. В Интернете доступно несколько реализаций, например здесь и здесь , но все они возвращают путь в виде списка узлов. Это проблематично для моей реализации,...
4859 просмотров
shortest-path dijkstra edges prolog
schedule 15.09.2023
Есть ли лучший способ, чем алгоритм Дейкстры, для поиска быстрейшего пути, не превышающего указанную стоимость
У меня проблема с поиском самого быстрого пути, который не превышает указанной стоимости. Есть аналогичный вопрос к этому, однако между ними есть большая разница. Здесь в данных могут появиться только те записи, которые ведут от более низкой точки к...
231 просмотров
algorithm dijkstra
schedule 07.03.2024
Настройка маршрутов Google для моего веб-сайта и/или моего приложения для Android
В настоящее время я наткнулся на карты направлений Google, где пользователь вводит начальный адрес и конечный адрес, после чего он генерирует маршрут от начального адреса до конечного адреса. Я обнаружил, что сгенерированный маршрут неэффективен и не...
122 просмотров
google-maps android dijkstra
schedule 01.05.2023
Перегрузка оператора 'operator()'
Я реализую алгоритм Дейкстры и хотел бы использовать «priority_queue» STL для ускорения процесса кодирования, но, как это часто бывает с моими попытками кодирования на C++, мое непонимание языка замедляет меня. Я нашел этот пример по адресу...
211 просмотров
c++ overloading operators dijkstra priority-queue
schedule 06.02.2022
Ошибка компиляции Boost d_ary_heap/priority_queue: удаленная функция
Я использую Dijkstra для поиска кратчайшего пути в графе. Раньше я использовал std::set, но я думаю, что куча могла бы работать лучше. Но у меня проблемы с использованием d_ary_heap или priority_queue. Это упрощенная версия: #include...
531 просмотров
c++ queue c++11 dijkstra heap
schedule 13.03.2023
Рекурсия и алгоритм Дейкстры
Мой рекурсивный алгоритм навигации по лабиринту занимает слишком много времени. Любые предложения о том, как ускорить его, чтобы быть более эффективным? Прямо сейчас он перебирает все возможные решения. Когда я пытался сократить это, он пропускал...
3073 просмотров
c# recursion dijkstra maze xna
schedule 10.03.2023
Почему A * работает быстрее, чем алгоритм Дейкстры?
Википедия говорит, что A * запускается в O (| E |), где | E | количество ребер в графе. Но мой друг говорит, что A * - это просто общий случай алгоритма Дейкстры, а алгоритм Дейкстры работает в O (| E | + | V | log | V |). Поэтому я не понимаю,...
2805 просмотров
algorithm a-star time-complexity big-o dijkstra
schedule 26.03.2024
Количество ребер в разреженном графе?
Я читал Алгоритм Дейкстры в гл. 24 и запутался со значением разреженного графа. Они говорят: «Если граф достаточно разреженный — в частности, E= o(V^2/lg V) — мы можем улучшить алгоритм, реализовав очередь с минимальным приоритетом с двоичной...
185 просмотров
algorithm dijkstra
schedule 04.06.2022
приоритетная очередь для алгоритма Дейкстры [закрыта]
Как работает приоритетная очередь? Я начал изучать алгоритм Дейкстры, погуглил и получил много кода, где разные кодеры использовали разные версии приоритетных очередей. В одном коде я заметил, что он использует это объявление priority_queue...
582 просмотров
c++ dijkstra
schedule 15.05.2023
реализация алгоритма Дейкстры с использованием приоритетной очереди
Я реализую алгоритм Дейкстры с использованием приоритетной очереди, мне нужна функция для удаления элемента из кучи, но я могу отправить ей только индекс вершины из главной Дейкстры, и я не могу найти его положение в куче, и я не могу позволить себе...
1827 просмотров
java algorithm dijkstra heap priority-queue
schedule 17.05.2022
Обозначение алгоритма Big O, состоящее из меньших алгоритмов
Я работаю над заданием, которое берет некоторый граф, добавляет к графу дополнительную вершину, применяет Беллмана Форда с новой вершиной в качестве источника, а затем использует применяет все пары Дейкстры к графу. Используемые алгоритмы имеют...
450 просмотров
runtime algorithm big-o dijkstra bellman-ford
schedule 06.01.2024
Как создать взвешенную матрицу смежности в Matlab
У меня есть набор данных в следующем формате: UID Lat Long LocID u1 lt1 lg1 l1 u1 lt2 lg2 l2 u1 lt3 lg3 l3 u2 lt4 lg4 l4 u3 lt1 lg1 l1 u3 lt4 lg4 l4 Отсюда мне...
1127 просмотров
matlab shortest-path dijkstra haversine adjacency-matrix
schedule 24.02.2023
Максимальная прибыль с использованием алгоритма Дейкстры
Алгоритм Дейкстры — один из самых быстрых алгоритмов решения задачи о кратчайшем пути. В моем случае сеть состоит из узлов, где вес преимущества — это прибыль, которую я получаю. Мне было интересно, смогу ли я обратить алгоритм Дейкстры, чтобы...
2828 просмотров
max algorithm shortest-path dijkstra
schedule 12.05.2023
Реализация алгоритма Дейкстры
Я видел алгоритм Дейкстры для взвешенных графов. Что мне делать, чтобы реализовать это, чтобы найти кратчайший путь в невзвешенном графе? Должен ли я считать веса между всеми ребрами 0 или 1? Во-вторых, я хочу реализовать bfs на 10^5 узлах,...
130 просмотров
graph dijkstra
schedule 28.04.2022
Как реализовать A* с минимальным количеством узлов на пути?
Я реализовал свой алгоритм A* таким образом, что он находит кратчайший путь к цели, учитывая, что он может перемещаться только в соседние/смежные ячейки. (Предположим, что узлы — это ячейки сетки). Таким образом, есть 8 окружающих клеток, которые он...
89 просмотров
algorithm path-finding a-star shortest-path dijkstra
schedule 17.04.2023
Оптимизация алгоритма Дейкстры
Мне нужен алгоритм поиска по графу, которого достаточно в нашем приложении для навигации роботов, и я выбрал алгоритм Дейкстры. Нам дана карта сетки, которая содержит свободные, занятые и неизвестные ячейки, где роботу разрешено проходить только...
1497 просмотров
c++ algorithm dijkstra multimap
schedule 23.04.2023