Вопросы с тегом «shortest-path»

Вопросы об алгоритмических проблемах поиска кратчайших путей между узлами в графе.

45
Минимальное связующее дерево против кратчайшего пути

В чем разница между алгоритмом минимального связующего дерева и алгоритмом кратчайшего пути? В моем классе структур данных мы рассмотрели два алгоритма минимального связующего дерева (Прима и Крускала) и один алгоритм кратчайшего пути (Дейкстры). Минимальное остовное дерево - это дерево в графе,...

24
Получение кратчайшего пути динамического графа

Я изучаю кратчайшие пути в ориентированных графах в настоящее время. Существует много эффективных алгоритмов для поиска кратчайшего пути в сети, например, dijkstra или bellman-ford. Но что, если график является динамическим? Говоря динамически, я имею в виду, что мы можем вставлять или удалять...

24
Какой самый быстрый алгоритм поиска всех кратчайших путей в разреженном графе?

В невзвешенном неориентированном графе с вершинами и ребрами, такими, что , каков самый быстрый способ найти все кратчайшие пути в графе? Можно ли сделать это быстрее, чем Флойд-Варшалл, который является но очень быстро за итерацию?E 2 V > E O ( V 3 )VVVEEE2V>E2V>E2V \gt EO(V3)O(V3)O(V^3)...

22
Сколько кратчайших расстояний изменяется при добавлении ребра на график?

Пусть G=(V,E)G=(V,E)G=(V,E) некоторый полный взвешенный неориентированный граф. Построим второй граф G′=(V,E′)G′=(V,E′)G'=(V, E') , добавив ребра одно за другим из в . Добавим края дляEEEE′E′E'Θ(|V|)Θ(|V|)\Theta(|V|)G′G′G' всего. Каждый раз, когда мы добавляем одно ребро (u,v)(u,v)(u,v) к E′E′E' ,...

20
Получение отрицательного цикла с помощью Bellman Ford

Я должен найти отрицательный цикл в ориентированном взвешенном графе. Я знаю, как работает алгоритм Беллмана Форда, и что он говорит мне, существует ли достижимый отрицательный цикл. Но это явно не называет это. Как я могу получить фактический путь цикла?v 1 , v 2 , … v k , v 1v1,v2,…vk,v1v1, v2,...

19
Кратчайший путь на неориентированном графе?

Поэтому я подумал, что этот (хотя и несколько базовый) вопрос относится к следующему: Скажем, у меня есть график размером 100 узлов, расположенных в виде шаблона 10x10 (подумайте, шахматная доска). График является ненаправленным и невзвешенным. Перемещение по графику включает перемещение трех...

16
Почему нельзя использовать DFS для поиска кратчайших путей в невзвешенных графах?

Я понимаю, что использование DFS «как есть» не найдет кратчайшего пути в невзвешенном графе. Но почему настройка DFS позволяет ему находить кратчайшие пути в невзвешенных графах с такой безнадежной перспективой? Все тексты на эту тему просто утверждают, что это невозможно сделать. Я не уверен (не...

15
Алгоритм Дейкстры на огромных графах

Я очень знаком с Dijkstra, и у меня есть конкретный вопрос об алгоритме. Если у меня есть огромный граф, например, 3,5 миллиарда узлов (все данные OpenStreetMap), то я явно не смог бы иметь граф в памяти, поэтому граф хранится на диске в базе данных. Есть библиотеки, доступные для вычисления...

14
Нахождение кратчайших и самых длинных путей между двумя вершинами в DAG

Учитывая невзвешенный DAG (направленный ациклический граф) D=(V,A)D=(V,A)D = (V,A) и две вершины sss и ttt , возможно ли найти кратчайший и самый длинный путь от sss до ttt за полиномиальное время? Длина пути измеряется количеством ребер. Я заинтересован в поиске диапазона возможных длин пути за...

14
Эффективная выборка самых коротких

Пусть GGG граф, и пусть sss и ttt две вершины GGG . Можем ли мы эффективно выбрать равномерно и независимо случайным образом кратчайший путь sss - ttt из множества всех кратчайших путей между sss и ttt ? Для простоты можно предположить, что GGG простая, ненаправленная и невзвешенная. Даже во многих...

14
Кратчайший непересекающийся путь для графа, вложенного в евклидову плоскость (2D)

Какой алгоритм вы бы использовали, чтобы найти кратчайший путь графа, который вложен в евклидову плоскость, чтобы путь не содержал каких-либо самопересечений (во вложении)? Например, на графике ниже вы хотите перейти от . Обычно такой алгоритм, как алгоритм Дейкстры, выдает такую...

14
Алгоритм Беллмана-Форда - Почему ребра могут быть обновлены не по порядку?

Алгоритм Беллмана-Форда определяет кратчайший путь от источника до всех других вершин. Первоначально расстояние между и всеми остальными вершинами установлено в . Затем вычисляется кратчайший путь от до каждой вершины; это продолжается для итераций. Мои вопросы:ssssss∞∞\inftysss|V|−1|V|−1|V|-1...

13
Как согласованность подразумевает, что эвристика также допустима?

Эвристическая функция ...h(n)h(n)h (n) Согласованно, если оценочная стоимость от узла до цели не превышает стоимость шага для его преемника плюс расчетную стоимость от преемника до цели.n ′nnnn′n′n' Допустимо, если никогда не переоценивает истинную стоимость состояния цели.h(n)h(n)h(n) В учебнике...

12
Почему мы не можем найти кратчайшие пути с отрицательными весами, просто добавив константу, чтобы все веса были положительными?

В настоящее время я читаю введение в алгоритмы и пришел по алгоритму Джонсона, который зависит от того, чтобы убедиться, что все пути положительны. алгоритм зависит от нахождения новой весовой функции (w '), которая является положительной для всех ребер и сохраняет правильность соотношений...

11
Что означает «ширина» в поиске ширины?

Я узнавал о широте первого поиска и вопрос пришел в голову , что , почему BFS называется так. В книге Введение в алгоритмы по КСПС , я прочитал следующую причину этого: Поиск в ширину так назван потому, что он расширяет границы между открывшимся и неоткрытых вершин равномерно по всей ширине...

10
Модификация алгоритма Дейкстры для весов ребер, взятых из диапазона

Предположим, у меня есть ориентированный граф с весами ребер, взятыми из диапазона где - константа. Если я пытаюсь найти кратчайший путь, используя алгоритм Дейкстры , как я могу изменить алгоритм / структуру данных и повысить сложность времени до ?K O ( | V | + | E | )[1,…,K][1,…,K][1,\dots,...

9
Нахождение k-кратчайшего пути между двумя узлами

Учитывая взвешенный орграф и весовую функцию , обычно можно использовать алгоритм Дейкстры для получения кратчайшего пути. Что меня интересует, так это как получить -короткий путь, -короткий путь и так далее.G = V, Eгзнак равноВ,ЕG=V,Ed( U , V )d(U,v)d(u,v)2н д2Nd2^{nd}3г д3рd3^{rd} Вопросов:...

9
Уникальный путь в ориентированном графе

Я разрабатываю алгоритм для класса, который будет определять, является ли ориентированный граф уникальным по отношению к вершине , так что для любого существует не более одного пути от до . Я начал с использования BFS (поиск в ширину), чтобы найти кратчайший путь от v до другой вершины u, а затем...