Алгоритм поиска кратчайшего питу на SQL

PG81
Дата: 30.04.2015 11:05:55
Всем привет!
имеется огромный граф (более 200 тыс вершин и ребер стока же)
находится в БД
реализовывал ли кто-нибудь алгоритмы поиска кратчайшего пути на SQL
Какой алгоритм выбрали? С какими сложностями столкнулись?
Щас сам сижу изучаю материал в тырнетах, интересно что люди скажут.
iap
Дата: 30.04.2015 11:07:50
PG81
более 200 тыс вершин и ребер стока же
C циклами значит?
PG81
Дата: 30.04.2015 11:13:47
iap,

да с циклами, не направленный
Сруль.
Дата: 03.05.2015 12:19:58
У каждой задачки, свой цимес.
Если с правильного хвоста начать, то доберёшься.
Чем больше времени тратишь до кода,
тем код легче.
Я бы начал с рекурсий.
От каждой вершины отходит дерево маршрутов.
Если научится при построении этого дерева, отбрасывать петли, т.е. те вершины, в которых ветка, уже отметилась,
то дерево получится простым.
Те ветки что приводят из пункта А в пункт Б, больше не разрабатывать и замерять.
Потом сравнить замеренные ветки.

В рекурсии, главное, это то условие, что стоит перед запуском
функции с новыми паратметрами, и отвчает на вопрос, а не пора ли
всё это закончить ?
Вот с него, я бы посоветовал начать.
Проверить его, до кишок, тогда не будет зацикливаний, а с остальным можно справиться.
Сруль.
Дата: 03.05.2015 12:30:19
Извините, за назойливость, но если вы нашли 1 маршрут, то все ветки, длиннее онного, можно, уже, не копать.
Оптимизация, типа.
Akina
Дата: 03.05.2015 22:26:03
Микроскопом можно забивать гвозди. Но надо ли?
SQL-сервер - не тот инструмент, который эффективно решает ТАКИЕ задачи.
Akina
Дата: 03.05.2015 22:27:48
Ну то есть можно, конечно, реализовать, например, волновой алгоритм с использованием CTE. Но вынос данных на клиента и применение там эффективных алгоритмов посика, думаю, намного разумнее и эффективнее.
Сруль.
Дата: 05.05.2015 11:17:03
Как говаривал один мой знакомый:
"В жизни бывает всё".
Как задачу поставят, так и спляшешь,
здравый смысл понятие расстяжимое.