Вопросы по теме 'dijkstra'
Как оптимизировать алгоритм Дейкстры для одного кратчайшего пути между двумя узлами?
Я пытался понять эту реализацию алгоритма Дейкстры на C и в то же время измените его так, чтобы был найден только кратчайший путь между двумя конкретными узлами (источник и пункт назначения).
Однако я не знаю точно, что делать. Как я это вижу,...
16138 просмотров
schedule
01.01.2023
Как увеличение веса ребра на графе повлияет на алгоритм Дейкстры?
Вопрос: рассмотрим ориентированный граф с 5 вершинами. Пусть алгоритм Дейкстры дает кратчайшие пути от узла s ко всем остальным узлам, как показано на рис. 1. Пусть вес ребра (x, t) увеличивается и предполагается, что все узлы каким-то образом...
1043 просмотров
schedule
04.03.2023
Расслабляет ли алгоритм Дейкстраса края кратчайшего пути по порядку?
В упражнении 24.3-5 «Введение в алгоритмы, 3-е издание» нужен пример того, что это неверно (не всегда верно). Это возможно? На мой взгляд, это невозможно, потому что каждое ребро расслаблено в то время, когда путь к текущей вершине уже определен....
7068 просмотров
schedule
25.05.2023
Дейкстра против Флойда-Уоршалла: поиск оптимального маршрута для всех пар узлов
Я читаю об алгоритме Дейкстры и алгоритме Флойда-Уоршалла. Я понимаю, что Dijkstra's находит оптимальный маршрут от одного узла ко всем другим узлам, а Floyd-Warshall находит оптимальный маршрут для всех пар узлов.
Мой вопрос: был бы алгоритм...
38531 просмотров
schedule
31.05.2022
Более 640 000 элементов в массиве — проблема с памятью [Dijkstra]
У меня есть скрипт, который помещает 803*803 (644 809) график со значением 1 000 000 внутри каждого. С ~500*500 все работает нормально, но теперь вылетает - пытается выделить больше 64 МБ памяти (чего у меня не было). Какое решение? Как-то...
644 просмотров
schedule
21.04.2023
Проблема алгоритма Дейкстры
Как применить алгоритм Дейкстры для графа, чтобы найти MST таким образом, чтобы результирующее дерево должно было иметь ребро между двумя заданными вершинами? (пример: MST должен включать ребро между X и Y)
Спасибо
726 просмотров
schedule
11.06.2022
Кратчайший путь с использованием алгоритма Дейкстры
В настоящее время я возрождаю старое домашнее задание, где я пишу программу, которая, помимо других функций, включает в себя поиск кратчайшего пути в графе с использованием алгоритма Дейкстры.
Я думаю, что по большей части я прав, но я продолжаю...
3073 просмотров
schedule
11.02.2023
Проверка веса отрицательного края в dijkstra_shortest_paths boost
Я использую библиотеку графов повышения, чтобы позвонить dijkstra_shortest_paths . Однако у меня есть кое-что особенное в том, что weight_map на самом деле является функтором. Следовательно, каждый раз, когда библиотеке boost требуется вес ребра,...
775 просмотров
schedule
07.08.2023
Создать список, используя определенные ключи в dict (python)?
Я реализую алгоритм поиска Дейкстры на Python. В конце поиска я восстанавливаю кратчайший путь, используя карту предшественника, начиная с предшественника узла назначения. Например:
path = []
path.append(destination)
previous =...
262 просмотров
schedule
22.03.2024
Входной файл для алгоритма Дейкстры
Мне трудно понять, как читать входной файл с помощью java. Файл имеет следующий формат:
u1 v1 w1
u2 v2 w2
...
um vm wm
-1
source
Каждая тройка обозначает ребро, которое определяется исходной вершиной, конечной вершиной и весом (пример:...
5977 просмотров
schedule
21.01.2023
Что не так с моим алгоритмом Дейкстры
Так что я работаю над этим часами, и я очень расстроен. Я не понимаю, что я делаю неправильно. Я использую алгоритм Дейкстры для поиска кратчайших путей между исходной вершиной и четырьмя другими вершинами, используя матрицу смежности. Идея...
484 просмотров
schedule
03.12.2022
что не так с моим алгоритмом Дейкстры для ненаправленного графа с одинаковым весом в perl. это не перестает повторяться
У меня есть взвешенный график для белковых узлов. Я писал программу на Perl, чтобы найти кратчайший путь для данного узла, используя алгоритм Дейкстры. Каждый белок (вершина) имеет одинаковый вес. Моя программа не останавливает итерацию и не дает...
774 просмотров
schedule
13.07.2023
алгоритм Дейкстры на iOS
Я отслеживаю местоположения и их связи с другими местоположениями. Я храню местоположения в NSArray, в то время как каждое местоположение представлено в виде словаря. Каждое местоположение имеет Словарь с атрибутами (locationName, Connections,...
4578 просмотров
schedule
11.07.2023
Найдите кратчайший путь с помощью Boost Dijkstra с указанным МАКСИМАЛЬНЫМ РАССТОЯНИЕМ
Мне нравится использовать реализацию dijkstra от boost, чтобы найти кратчайший путь от узла
Однако в моей текущей проблеме у меня огромный граф, и мне нужно только найти кратчайшие пути к узлам, которые находятся на определенном расстоянии.
Я...
671 просмотров
schedule
17.01.2024
как преобразовать этот код из Dijkstra в Astar?
Итак, у меня есть проект, в котором я хочу перейти на Astar из-за скорости.
Но C++ не моя сильная сторона. Может ли кто-нибудь помочь мне (или сказать мне, как это сделать..), преобразовав алгоритм из Дейкстры в Астар?
Я нашел эту реализацию...
2091 просмотров
schedule
13.07.2022
Прав ли я насчет различий между алгоритмами Флойда-Уоршалла, Дейкстры и Беллмана-Форда?
Я изучал эти три и делаю выводы из них ниже. Может ли кто-нибудь сказать мне, достаточно ли я их понял или нет? Спасибо.
Алгоритм Дейкстры используется только тогда, когда у вас есть единственный источник и вы хотите знать наименьший путь от...
20809 просмотров
schedule
13.09.2022
лучшая структура Graph для реализации Дейкстры в прологе
Вопрос простой. Как я могу построить свой график в прологе SWI для реализации алгоритма Дейкстры?
Я нашел это , но это слишком медленно для моей работы.
1427 просмотров
schedule
23.07.2023
Дейкстра: найти кратчайший путь в ориентированном графе
Рассмотрим ориентированный граф, показанный на рисунке ниже. Существует несколько кратчайших путей между вершинами S и T. Какой из них будет сообщен алгоритмом кратчайшего пути Дейстры? Предположим, что на любой итерации кратчайший путь к вершине v...
17333 просмотров
schedule
04.10.2022
Бесконечный цикл в алгоритме Дейкстры?
Я пытаюсь реализовать алгоритм Дейкстры, чтобы найти кратчайший путь между двумя пересечениями (вершинами) в графе. К сожалению, я получаю бесконечный цикл в цикле while, и я не могу понять, почему.
NodeDist представляет собой хэш-карту между...
1502 просмотров
schedule
02.10.2022
Дейкстра на сетке
Нет смысла использовать приоритетную очередь, если я запускаю алгоритм dijskstra в «сетке», верно?
Сетка будет такой картой: Вершины:
___________________
|A|_|_|_|_|_|_|_|_|_|
|C|B|_|_|_|_|E|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|...
1123 просмотров
schedule
31.01.2023
