Публикации по теме 'floyd-warshall'
Умножение матриц кратчайшего пути по всем парам Флойда-Уоршалла
Цель алгоритма Флойда-Уоршалла - найти кратчайшие пути в дереве с помощью динамического программирования. Начнем с примера.
Алгоритм Флойда-Уоршалла начинается со сбора исходных весов и их помещения в матрицу. Поскольку имеется 4 вершины, матрица будет иметь 4 строки и 4 столбца.
Начиная с вершины 1, алгоритм собирает начальные веса от 1 до 3 других вершин. Он поместит 0 для себя и бесконечности, если нет прямого пути. Вес ребра от 1 до самого себя равен 0. Вес ребра от 1..
Вопросы по теме 'floyd-warshall'
Оптимизируйте Флойда-Уоршалла для симметричной матрицы смежности
Существует ли оптимизация, снижающая постоянный коэффициент времени выполнения Флойда-Уоршалла, если у вас гарантированно будет симметричная матрица смежности?
3949 просмотров
schedule
01.01.2024
Логика алгоритма Флойда-Уоршалла - застрял
Я пытаюсь использовать эту логику, чтобы понять, что происходит с матрицей смежности , но я Я массивно запутался, где говорится о интервалах для abcd .....
Может ли кто-нибудь объяснить, что здесь происходит?
Спасибо (помечено как java,...
7677 просмотров
schedule
08.01.2024
Как вывести кратчайший путь в алгоритме Флойда-Уоршалла?
Я пытаюсь реализовать алгоритм Флойда-Уоршалла (кратчайший путь для всех пар). В приведенном ниже коде, когда я ввожу несколько чисел, в качестве ввода выдается последнее число. Я знаю, что код не полный.
Что мне теперь делать, чтобы напечатать...
11688 просмотров
schedule
11.04.2023
матрица смежности/Floyd/Warshall в lisp
Очевидно, мой учитель считает, что даже если у нас нет времени на изучение материала (и недостаточно примеров), мы должны двигаться дальше, поэтому теперь мне нужно знать, как сделать алгоритмы Флойда-Уоршалла и Уоршалла в clisp.
Как и в случае с...
844 просмотров
schedule
26.04.2023
Как перечислить вершины, пройденные в алгоритме Флойда-Уоршалла
Кажется, я не могу найти способ перечислить вершины, пройденные, поскольку мой алгоритм (floyd-warshall) вычисляет кратчайший путь. Мне сказали, что мне придется использовать рекурсию, но я не знаю, как ее использовать. Пожалуйста, дайте...
2426 просмотров
schedule
28.12.2022
Алгоритм Флойда-Уоршолла
Есть ли простое объяснение, почему этот фрагмент находит кратчайшее расстояние между двумя вершинами?
for (k = 0; k < n; ++k)
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
if (d[i][k] + d[k][j] < d[i][j])
d[i][j]...
1510 просмотров
schedule
16.04.2022
Алгоритм Флойда Уоршелла для поиска кратчайшего пути
Я просматривал некоторые старые конкурсные вопросы и нашел этот, он выглядел забавно, http://dwite.ca/old/Problem5Jan2006.pdf , я пытался использовать алгоритм Флойда Варшалла, чтобы получить кратчайший путь от любого узла к любому другому узлу, вы,...
3947 просмотров
schedule
23.05.2022
Почему Флойд-Уоршалл странным образом помнит путь?
Я только начал изучать алгоритм для графов, а точнее - алгоритм Флойда-Уоршалла. Глядя в википедию на алгоритм, измененный для обеспечения возможности восстановления пути, я заметил, что он сохраняет промежуточный узел вместо более логичного (на...
564 просмотров
schedule
06.01.2023
Алгоритм Флойда-Уоршалла - представление бесконечности
Как мне представить бесконечность при реализации на Java, используя алгоритм Флойда-Уоршалла для поиска кратчайшего пути между двумя вершинами? Я использую бесконечность, чтобы сказать, что между двумя вершинами нет пути.
Спасибо
1226 просмотров
schedule
26.03.2022
Флойд-Уоршалл не может понять, что не так
Мне нужна новая пара глаз для этого, по какой-то причине она не генерирует правильные матрицы последовательности и расстояния. Ниже приведена моя реализация.
Это в С#, а DistanceMatrix — это двойной [,] а SequenceMatrix — это строка [,]
они...
225 просмотров
schedule
17.03.2023
Как прочитать этот ввод графа и поместить в матрицу смежности?
Я запутался и пытаюсь понять, как поместить эти данные графика в матрицу смежности.
Это пример ввода из текстового файла:
0 1,28 3,33
1 2,10 4,44
2 3,50
3 4,30
4
Вот так должна выглядеть матрица
0 1 2 3 4
0 INF 28 INF 33...
832 просмотров
schedule
03.09.2022
получение неправильного вывода для параллельного алгоритма Floyd Warshall в OpenCL
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
/*#ifdef __APPLE__
#include <OpenCL/opencl.h>
#else*/
#include <CL/cl.h>
//#endif
#define DATA_SIZE 16
using namespace std;
const char *ProgramSource =...
317 просмотров
schedule
11.06.2023
Найдите кратчайший путь с помощью алгоритма Флойда
У меня есть матрица смежности, которая содержит числа 0 и 1. Если нет ребра от одного узла к другому, поле будет равно 0, в противном случае поле будет помечено как 1.
Тогда, если поле в матрице смежности было 0, между узлами нет ребра, иначе есть...
943 просмотров
schedule
27.07.2022
Инициализация графа с использованием словарей для алгоритма флойд на неориентированных графах?
Хотелось бы узнать, как реализовать флойд на неориентированном графе. В этой реализации
for k in graph:
for i in graph:
for j in graph:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] +...
379 просмотров
schedule
10.04.2022
Временная сложность алгоритма Флойда Уоршалла на отрицательных весовых циклах
Я знаю, что нет способа найти минимальное расстояние, когда на графике есть отрицательные весовые циклы, не будет никакого значения минимального расстояния. Мой вопрос: что произойдет, если мы скормим алгоритму Флойда Уоршалла графами с...
491 просмотров
schedule
02.04.2023
Алгоритм Флойда-Уоршалла возвращает каждый кратчайший путь с одинаковым весом.
Как мне получить каждый кратчайший путь от вершины 1 к вершине 10, имеющий одинаковый вес, с помощью алгоритма Флойда-Уоршалла? Мне удалось получить общее количество всех кратчайших путей от вершины 1 до вершины 10.
public static int[][]...
307 просмотров
schedule
31.12.2022
Алгоритм Флойда Уоршалла не работает должным образом
Я пытаюсь реализовать алгоритм Варшалла в python 3, чтобы создать матрицу с кратчайшим расстоянием между каждой точкой.
Предполагается, что это простая реализация, я создаю матрицу и заполняю ее расстоянием между каждой точкой.
Однако я получаю...
149 просмотров
schedule
07.04.2023
Алгоритм Флойда Уоршалла на графе
Я пытаюсь найти кратчайший путь ко всем узлам графа, используя алгоритм Флойд Варшалла для класса. Мне дали базовый код для графа, и я попытался реализовать алгоритм с помощью псевдокода, но так и не понял, как выбрать конкретное ребро на основе...
364 просмотров
schedule
25.07.2022
