Вопросы по теме 'shortest-path'
Какой алгоритм я могу использовать для поиска кратчайшего пути между указанными типами узлов в графе?
Это проблема:
У меня есть n точек (p1, p2, p3, .. pn), каждая из них может соединиться с любой другой с определенной стоимостью x.
Каждая точка принадлежит к одному из множества типов точек (например, "A", "B", "C", "D"...).
Ввод метода - это...
3215 просмотров
schedule
27.02.2024
Алгоритмы для двунаправленных графов
Скажем, у меня есть граф (сеть) узлов со следующими весовыми коэффициентами: 1. путешествие в одну сторону по звену между двумя узлами. 2. Путешествие в обратном направлении по звену между двумя узлами (они могут быть разными). 3. переход с одной...
4688 просмотров
schedule
03.11.2023
Есть ли алгоритм для вычисления кратчайшего дерева (не пути)?
Привет Перецветы,
У меня есть взвешенный ориентированный граф, и мне нужно дерево с наименьшей стоимостью, охватывающее все узлы, где корнем является конкретный заданный узел графа. Я не знаю, могу ли я также установить другое максимальное...
223 просмотров
schedule
04.01.2024
Кратчайшее расстояние в логарифмическом полукольце для взвешенного автомата
Я думал, что понял это... но я до сих пор не могу понять это. Я играю с OpenFst и пытаюсь понять, как вычисляется «кратчайшее расстояние» в полукольце «журнал». Для следующего маленького автомата
http://i.imgur.com/FThh6.png
Результат...
532 просмотров
schedule
16.02.2024
Реализация алгоритма Дейкстры с использованием минимальной кучи, но не удалась
Я пытаюсь реализовать Dijkstra's Algorithm с помощью минимальной кучи в java, но каждый раз получаю неправильный вывод. Здесь я нашел ту же тему на С++. Ниже мой график. Узел A, окрашенный в зеленый цвет, является источником, а узел F,...
6005 просмотров
schedule
16.03.2024
Как вы используете двунаправленную BFS для поиска кратчайшего пути?
Как вы используете двунаправленную BFS для поиска кратчайшего пути? Допустим, есть сетка 6x6. Начальная точка находится в (0,5), а конечная точка — в (4,1). Каков кратчайший путь с использованием двунаправленного BFS? Стоимость пути отсутствует....
21860 просмотров
schedule
18.03.2024
Как получить кратчайший путь между двумя точками в картах Google
Я не знаю, является ли это собственностью Google или его открытым исходным кодом. Мне нужно знать, как Google показывает различные маршруты, а также самый короткий из них на основе доступной дороги . Потому что я создал приложение Google Maps, в...
16556 просмотров
schedule
19.12.2023
Направление кратчайшего пути в Android
Я новичок в Google Maps V2, я хочу найти кратчайший путь для моего текущего местоположения и места назначения. Итак, я попробовал некоторый код, и он работает, но не рисует кратчайший путь. мне нужна помощь пожалуйста:
Вот мой код:
gps = new...
1040 просмотров
schedule
19.09.2022
Дорожная карта с туннелями
Учитывая дорожную карту между несколькими городами, с дорогами между двумя городами, содержащими туннели, ваша цель состоит в том, чтобы найти кратчайшие возможные пути между начальным городом и всеми другими городами так, чтобы каждый путь содержал...
110 просмотров
schedule
24.10.2022
Полный граф только с двумя возможными затратами. Какова стоимость кратчайшего пути от 0 до N - 1
Вам дан полный неориентированный граф с N вершинами. Все ребра, кроме K, имеют стоимость A. Эти K ребер имеют стоимость B, и вы знаете их (как список пар). Какова минимальная стоимость от узла 0 до узла N - 1.
2 <= N <= 500k
0 <= K...
989 просмотров
schedule
04.04.2024
Набор кратчайших путей с несколькими начальными и множественными концами
У меня проблема с кратчайшим путем в ориентированном взвешенном графе. Я знаю Dijkstra , BFS , DFS . Однако у меня есть a set of vertices S для отправных точек и a set of vertices E to end . S и E не пересекаются. Итак, как я могу найти...
1978 просмотров
schedule
26.11.2023
Кратчайший путь, соединяющий n точек
У меня есть n точек, и мне нужно соединить их все, чтобы минимизировать конечное расстояние. На изображении выше представлен алгоритм, который в каждом узле соединяется с ближайшим, но окончательный результат может быть действительно таким.
Я...
1172 просмотров
schedule
23.05.2024
Найдите кратчайший путь между двумя узлами в ориентированном взвешенном графе
У меня есть ориентированный взвешенный граф G = <V, E> . Мне нужно найти кратчайший путь между s и t в O((V + E)*logV) . Это была бы очень простая задача, если бы у меня был классический метрический вес пути. Но это не так.
Weight...
2754 просмотров
schedule
21.01.2024
Расчет между 2 точками в 2D-массиве
Я делаю карту 2D-массива, например:
* 0 1 2 3 4 5 6
0 # # # # # P #
1 # # # # # # #
2 # # # # # # #
3 # # T # # # #
4 # # # # # # #
Это игра. «Т» — Тролль, а «П» — Игрок. Тролль преследует игрока в этой игре. Предположим, что игрок теперь...
2672 просмотров
schedule
05.06.2024
Кратчайший путь двух вершин в остовном дереве с ребрами на одинаковом расстоянии
У меня есть остов графа, начиная с вершины v. Все ребра находятся на одном расстоянии (скажем, 1).
Как определить кратчайший путь из v в другую вершину u?
65 просмотров
schedule
21.11.2022
построить граф, в котором дерево кратчайших путей длиннее минимального остовного дерева
Создайте пример графа, в котором дерево кратчайшего пути длиннее минимального связующего дерева.
В худшем случае, насколько кратчайшее дерево пути может быть длиннее минимального остовного дерева?
480 просмотров
schedule
13.12.2023
Реализация кратчайшего пути из одного источника: приоритет по сравнению с очередью FIFO
В зависимости от специфики проблемы в контексте задачи о кратчайшем пути с одним источником обычно упоминаются два алгоритма: алгоритм Дейкстры и алгоритм Беллмана-Форда. Алгоритм Дейкстры работает с положительными весами ребер, тогда как алгоритм...
909 просмотров
schedule
01.05.2024
Посещение выбранных точек в сетке перед достижением пункта назначения с использованием BFS
Итак, я реализовал решение проблемы, которая началась с того, что я дал вам сетку (n,n). Мне потребовалось начать с (1,1), посетить определенные точки в сетке, отмеченные *, а затем, наконец, перейти к (n,n). Гарантируется, что размер сетки не...
1088 просмотров
schedule
23.02.2024
Влияние на кратчайшие пути после удаления ребер
Был предоставлен ввод ориентированного графа, и я нашел кратчайшие пути к конкретному узлу «T», используя как асинхронный, так и синхронный алгоритм Беллмана-Форда. Я пытался выяснить влияние на кратчайшие пути после удаления некоторых ребер. В...
232 просмотров
schedule
03.11.2022
минимизация затрат на поездки между городами
Привет, у меня есть проблема оптимизации, когда у меня есть n дней, чтобы поехать в k городов, и я должен спланировать свое путешествие так, чтобы моя общая стоимость поездки была минимизирована.
Стоимость проезда между любыми двумя городами u и v...
148 просмотров
schedule
28.01.2024
