Самый длинный путь в графе с использованием SQL

У меня есть график, который сохраняется в виде двух таблиц с именами Edge и Node в SQL следующим образом:

Node table:
Id Name
10 A
11 B
12 C

Edge Table:
From To Weight
10 11 0.3
10 14 0.2
10 12 0.5
11 12 0.6
12 10 0.8

Например, одно возможное решение для пути от узла 10 к узлу 12 выглядит следующим образом:

From    To  Weight  Path
10  12  0.9 10,11,12

Теперь я хочу найти самый длинный путь между узлами графа (для любого возможного пути).

Я изменил dijkstra с отрицательными краями, и он зациклился и не вернул никакого результата.

Есть ли какая-то процедура или алгоритм, чтобы узнать желаемый результат?


sql sql-server graph longest-path
person Siavash R    schedule 20.07.2016    source источник
comment
Я предлагаю вам SQL граф блокировки в Google. Пытается выполнить несколько выходов, а затем вернуться к SO при возникновении проблемы. Да, есть функции, но мы не делаем домашние задания бесплатно. ;)   -  person clifton_h    schedule 21.07.2016
comment
@clifton_h это не домашнее задание, и я сделал то, что вы сказали. ТАК было последним местом, где я искал свою проблему. Это часть реализации моего анализа социальных сетей.   -  person Siavash R    schedule 21.07.2016
comment
Можете ли вы показать код того, что вы, может быть, пробовали?   -  person bobkingof12vs    schedule 21.07.2016
comment
@clifton_h вы сказали, что в Google доступны некоторые источники по моей теме. Скажите, пожалуйста, где они?   -  person Siavash R    schedule 21.07.2016
comment
@ bobkingof12vs В настоящее время я реализовал алгоритм Дейкстры с SQL, который не находит самый длинный путь   -  person Siavash R    schedule 21.07.2016
comment
Один полезный фрагмент был написан мировым финалистом ACM ICPC на QUORA. Поскольку сложные алгоритмы не являются типичным SQL-запросом, я думаю, что лучше всего избегать использования тегов SQL при поиске. Программисты в любом случае занимаются алгоритмами, и ваша проблема, возможно, связана с b-деревьями и другими методами иерархических отношений.   -  person clifton_h    schedule 21.07.2016
comment
Дейкстра находит кратчайший путь, если мне не изменяет память. Но его можно изменить, чтобы найти самый длинный путь, если вы оптимизируете более 1 / w вместо w (w - это набор весов ребер).   -  person Ben Thul    schedule 22.07.2016
comment
@BenThul Я думаю, что изменение веса ребер - плохое предложение. Он не отличается от фактического веса. Если мы умножим веса на -1, мы сможем использовать Дейкстру. Но проблема в циклах и отрицательных циклах.   -  person Siavash R    schedule 23.07.2016

Ответы (1)


arrow_upward
0
arrow_downward

Недавно у меня была аналогичная проблема, и я пытался найдите самый длинный путь с помощью SQL-рекурсивного запроса CTE. Пожалуйста, обратитесь к данной статье.

Я попытался изменить указанное выше решение для вашей проблемы и получить список всех возможных путей, как показано на следующем экране вывода.

введите описание изображения здесь

Если вы хотите добиться именно такого результата, я могу продолжить описание своего решения на SQL Server.

Указанный SQL-запрос вычисляет самый длинный путь для данных двух узлов. Итак, прежде всего нам нужно определить все возможные начальные и конечные узлы.

В запросе ниже перечислены все возможные наборы.

select Nodes_From.Id as [From], Nodes_To.Id as [To]
from LongestPath_Nodes as Nodes_From
inner join LongestPath_Nodes as Nodes_To
    on Nodes_From.Id <> Nodes_To.Id

Обратите внимание, что это исключает, например, "14", поскольку его нет в таблице узлов (поэтому на самом деле существует проблема согласованности в данных тестовых данных)

Итак, создав курсор SQL, я могу пройти через каждый набор узлов (от-до комбинация узлов) и выполнить хранимую процедуру, которая включает в себя коды SQL, вычисляющие самый длинный путь для данных двух узлов из указанной статьи

Я также создал таблицу для хранения общего веса пути.

Create Table LongestPath_Routes ([weight] decimal(10,1), path varchar(100))

Как видно из приведенного ниже сценария SQL, я очищаю эту таблицу в начале. Затем заполните его для каждого набора узлов от-до в хранимой процедуре. Наконец, после завершения выполнения курсора я запрашиваю таблицу путем сортировки по столбцу веса для самого длинного пути (также возможен самый короткий путь)

truncate table LongestPath_Routes

DECLARE @From TinyInt
DECLARE @To TinyInt

DECLARE PathCursor CURSOR FAST_FORWARD FOR
    select Nodes_From.Id as [From], Nodes_To.Id as [To]
    from LongestPath_Nodes as Nodes_From
    inner join LongestPath_Nodes as Nodes_To
        on Nodes_From.Id <> Nodes_To.Id

OPEN PathCursor

FETCH NEXT FROM PathCursor INTO @From, @To

WHILE @@FETCH_STATUS = 0
BEGIN
set nocount on
 EXEC LongestPath_Calculate_for_Nodes @From, @To
set nocount off

 FETCH NEXT FROM PathCursor INTO @From, @To
END

CLOSE PathCursor
DEALLOCATE PathCursor 

select * from LongestPath_Routes order by [weight] desc

Надеюсь, это решение вам поможет

person Eralper    schedule 30.03.2018