Публикации по теме 'floyd-warshall'
Понимание алгоритма Флойда-Уоршалла
Первоначально опубликовано на Seedbx.com 2 декабря 2020 г.
Поиск кратчайшего пути во взвешенном графе — сложная задача, но поиск кратчайшего пути из каждой вершины в любую другую вершину — непростая задача.
В этом посте мы обсудим алгоритм Флойда-Уоршалла, который идеально подходит для этой работы.
Примечание . Во всех псевдокодах используется индексация на основе 0, а отступы используются для различения блоков кодов.
Постановка задачи
Пусть G — взвешенный ориентированный..
Вопросы по теме 'floyd-warshall'
Флойд Уоршалл: вычисление топ-k кратчайших путей на пару вершин
В алгоритме Флойда-Уоршалла стоимость кратчайшего пути вычисляется для любой пары вершин. Дополнительная бухгалтерия позволяет нам вести фактический путь (список вершин) на кратчайшем пути.
Как я могу расширить Флойда-Уоршалла так, чтобы для любой...
1006 просмотров
schedule
14.07.2022
Найдите кратчайший (скорейший) путь в трех измерениях между определенными точками
Вот моя формулировка проблемы:
У меня есть куб с указанными размерами. со временем в этом кубе генерируются несколько шаров. Я смоделировал координаты (местоположение x, y, z), время генерации и размер шаров. Теперь мне нужно найти кратчайший...
404 просмотров
schedule
22.07.2023
Python – как я могу извлечь весь кратчайший путь из этого сетевого кода?
Я попытался запустить это, и я получаю кратчайший путь с адресом памяти. Как я могу удалить адрес памяти из вывода
import networkx as nx
G=nx.Graph()
G.add_nodes_from([1,2,3,4])
G.add_weighted_edges_from([(1,2,8),(1,3,5),(2,4,1),(3,4,2)])...
366 просмотров
schedule
15.08.2023
Выступление Флойда-Уоршалла на Swift 3
Я относительно новичок в Swift, поэтому я, вероятно, сделал что-то глупое.
Я реализовал код, очень похожий на этот, на Java, и алгоритм выполняется менее чем за 1 секунду на графе с 800 вершинами. Однако версия Swift 3 занимает более 5 минут на...
168 просмотров
schedule
26.12.2022
Как найти общее количество всех минимальных путей между s и t через v в графе?
Я хочу найти общее количество всех минимальных путей между s и t через v в графе, где s, t и v являются узлами графа, используя алгоритм Флойда Уоршалла. Заранее спасибо за ваши ответы.
79 просмотров
schedule
14.01.2023
Вычислить разреженное транзитивное закрытие scipy разреженной матрицы
Я хочу вычислить транзитивное замыкание разреженной матрицы в Python. . В настоящее время я использую разреженные матрицы scipy.
Степень матрицы (в моем случае **12 ) хорошо работает на очень разреженных матрицах, какими бы большими они ни...
808 просмотров
schedule
05.05.2022
Алгоритм Флойда Уоршалла параллельно с использованием cuda
Я пытаюсь реализовать алгоритм Флойда Уоршалла с помощью cuda, но у меня проблема с синхронизацией. Это мой код:
__global__ void run_on_gpu(const int graph_size, int *output, int k) {
int i = blockDim.y * blockIdx.y + threadIdx.y;
int j =...
105 просмотров
schedule
08.10.2022
