Описание тега floyd-warshall
Алгоритм Флойда-Уоршалла представляет собой алгоритм O(|V|^3) для вычисления кратчайших путей для всех пар в ориентированном взвешенном графе.
1
ответ
Алгоритм Флойда – Варшалла с реконструкцией пути не находит путь
Я пытаюсь найти кратчайший путь между источником и целью, используя алгоритм Флойда-Варшалла, вычисляя кратчайшие пути между всеми парами. Мне нужно найти кратчайший путь, а не только расстояние. Вот что я пытаюсь сделать: Я храню первую вершину на …
01 апр '14 в 14:38
1
ответ
Найти кратчайший путь с помощью алгоритма Флойда
У меня есть матрица смежности, которая содержит числа 0 и 1. Если нет ребра от одного узла к другому, поле будет 0, в противном случае поле будет помечено как 1. Тогда, если поле в матрице смежности было 0, ребро между узлами отсутствует, в противно…
25 июн '15 в 14:32
1
ответ
Алгоритм Флойд-Уоршалла
В настоящее время я работаю над небольшим проектом защиты башни на Java, и я застрял с поиском пути. Я много читал об A* dijkstra и подобных вещах, но я решил, что, вероятно, лучше всего использовать Floyd-Warshall для поиска пути (по крайней мере, …
11 апр '12 в 09:16
1
ответ
Реконструкция пути Флойд-Варшалл без рекурсии
Я использую этот алгоритм Флойда-Варшалла отсюда. import static java.lang.String.format; import java.util.Arrays; public class FloydWarshall { public static void main(String[] args) { int[][] weights = {{1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {…
24 май '18 в 21:06
1
ответ
Алгоритм Флойда-Варшалла - кратчайший путь - сохранить индекс путей в массив
Я реализую алгоритм Флойда-Варшалла для симметричного, неориентированного графа. На данный момент я рассчитал лучший путь для каждой точки подключения. Моя проблема заключается в том, что я хочу сохранить индексные точки, рассчитанные для накопленно…
30 дек '16 в 17:09
1
ответ
Алгоритм Флойда-Варшалла, работающий с отрицательными циклами
Как можно изменить алгоритм Флойда-Варшалла, чтобы найти кратчайший путь любого цикла отрицательной стоимости ориентированного графа, который поддерживает O(V^3) временную сложность?
24 фев '15 в 18:46
0
ответов
Путь алгоритма Флойда-Уоршолла между двумя вершинами (неориентированный граф)
Мне нужна ваша помощь с алгоритмом FW. У меня вопрос: можно ли найти кратчайший путь между двумя вершинами? Ниже я приведу пример того, чего я хочу. 1 -----50(w)----- 5 | \__ / | | \5(w) /20(w)| 10(w) \__3__/ |25(w) | \___ | | 18(w)\ | 2--------8(w)…
21 май '16 в 10:23
1
ответ
Ошибка сегментации векторной вставки вторая итерация
Я на самом деле пытаюсь реализовать алгоритм Уолшолла Флойда, но я столкнулся с трудностью. У меня ошибка сегментации, когда я пытаюсь найти кратчайший путь в моей матрице последовательности. Я следую этому уроку: алгоритм Флойд Уорсхолла Все работа…
12 янв '15 в 20:13
1
ответ
Сетевой судья PS [Floyd_Warshal, C++]
Я решаю эту проблему https://www.acmicpc.net/problem/1238 Вы можете изменить язык, нажав кнопку Идея, которую я придумал, состоит в том, чтобы найти сумму кратчайшего расстояния от Kth до второго и второго до Kth. так вот весь мой исходный код #incl…
27 фев '17 в 12:02
2
ответа
Алгоритм Флойда-Варшалла кратчайшего пути
Я реализовал алгоритм Флойда-Варшалла. В соответствии с их матрицами я могу получить правильный результат о кратчайшем пути между двумя местами и их расстоянии. У меня вопрос, как распечатать кратчайшее расстояние от i до j. Я провел несколько иссле…
11 июн '12 в 08:14
1
ответ
Java: ссылка на ребро в графе
Я модифицирую реализацию графа, чтобы вычислить матрицу кратчайшего пути всех пар, используя алгоритм Флойда. Граф имеет как смежный список, так и матричные реализации. Сейчас я использую матрицу смежности, потому что она нужна для этого алгоритма. …
29 июн '10 в 17:58
1
ответ
Нахождение всех вершин на отрицательных циклах
Я знаю, что проблема проверки того, принадлежит ли данное ребро взвешенного орграфа отрицательному циклу, является NP-полной ( нахождение минимального подграфа, содержащего все отрицательные циклы), и Беллман-Форд позволяет проверять вершину на то ж…
23 май '13 в 17:52
0
ответов
Кратчайший путь между каждой парой узлов в графике А / или?
У меня есть график зависимостей AND/OR, где узлы являются веб-службами, и между двумя службами есть дуга S1 ->S2, если некоторые выходные данные S1 похожи на некоторые входные данные S2 Вес дуги является функцией многих параметров (пример: время вып…
30 мар '17 в 12:02
1
ответ
Использование Флойд-Варшалла для выявления положительных циклов
Я видел, как люди говорили, что Флойд-Варшалл может быть модифицирован (легко) для обнаружения циклов. Примечание: я предполагаю, что график не имеет отрицательных циклов. Я хочу знать, как изменить алгоритм? И почему это правильно? Кроме того, каки…
06 дек '13 в 20:20
0
ответов
SPARQL Флойд-Варшалл (или другой APSP)
Мне нужна эффективная реализация APSP для SPARQL. В настоящее время у меня есть работающий Floyd-Warshall, управляемый python, но он использует обновление в каждой итерации самого внутреннего цикла. Чтобы перебрать все узлы, я помещаю все узлы в спи…
30 июл '13 в 19:13
1
ответ
Сложность времени выполнения Флойда Уоршалла с точки зрения ребер
Выразите время выполнения Θ() алгоритма Флойда-Варшалла для задачи кратчайшего пути всех пар для графа G(V, E): i. В терминах количества вершин V в G. ii. В терминах числа ребер E в плотном графе G. iii. В терминах числа ребер E в разреженном графе …
14 сен '17 в 03:56
1
ответ
MPI объединяет массивы из всех рангов по порядку
Я новичок в MPI У меня есть несколько массивов, сгенерированных процессорами. Каждый процессор генерирует один массив разной длины. Как я могу объединить их все в порядке в один массив, хранящийся только в процессоре 0. Например: Processor 0: [1 1 1…
21 сен '13 в 08:09
0
ответов
Алгоритм поиска пути - несколько задач
У меня есть проект для школы, где я должен найти кратчайший доступный маршрут между двумя узлами, используя алгоритмы Флойда Варшалла и Дейкстры. Все хорошо, однако, в дополнение к этому я должен предоставить поправку к обоим алгоритмам, чтобы вычис…
04 апр '14 в 18:37
1
ответ
Расстояние между узлами во Флойд Уоршолл
Эта страница википедии объясняет алгоритм Флойда Варшалла, чтобы найти кратчайший путь между узлами в графе. Страница википедии использует график слева от изображения как начальный график (до первой итерации, когда k = 0), а затем показывает оставш…
11 дек '16 в 14:18
1
ответ
Как вывести список вершин, переданных в алгоритме Флойда-Варшалла
Кажется, я не могу найти способ перечислить переданные вершины, поскольку мой алгоритм (floyd-warshall) вычисляет для кратчайшего пути. Мне сказали, что мне придется использовать рекурсию, но я не знаю, как использовать рекурсию. Пожалуйста, дайте п…
17 май '12 в 15:29