Графы

Необходимы алгоритмы поиска пути в не древовидных графах.
Если кто обладает какой информацией - подсобите.

Цитата GrAnd, 10.06.02, 12:51:41

Необходимы алгоритмы поиска пути в не древовидных графах.
Если кто обладает какой информацией - подсобите.

Есть алгоритм, для любого _связного_ графа строящий матрицу расстояний.
Иначе - ругается и вылетает.
Если подойдет - мыль.

Куда мылить то я адреса то не вижу

Цитата GrAnd, 11.06.02, 16:11:09

Куда мылить то я адреса то не вижу

А чем Дийкстра то не подходит?
http://algolist.manual.ru/maths/graphs/index.php

Проблема в том, что графы могут быть как замкнутыми , так и циклическими.
А Дийкстра слабовата в этом : : :

Для Дийкстры есть только 1 ограничение:
Не должно быть ребер с отрицательным весом.
На все остальное ему начхать.

Итак, думаю надо предоставить полную формулировку задачи.
Фактически есть бесконечное множество точек плоскости (узлов графа)  некоторые их них соеденены между собой (ребра). Количество соединений для каждой точки не ограничено. Таким образом они образуют равнозначный, не древовидный граф. Задача сводится к тому, чтобы из любого узла данного графа найти кратчайший путь к заданной точки. Вариантов пути может быть несколько, а может и не одного.
Для циклической структуры графа (например пересекающиеся спирали) твой алгоритм приводит либо к полному зацикливанию, либо находит абсолютно не верное решение

Скорее всего, ты неверно реализовал Дийкстру. Зацикливания быть в принципе не может, т.к. алгоритм помечает вершины, занесенные в маршрут. При возвращении на них длина пути растет и они пропускаются. Насчет неверного решения - весьма странно, т.к. алгоритм характерен тем, что заносит вершину "к" в маршрут, только после того, как известно, что путь от начала до "к" - кратчайший.
Короче ищи глюк или покажи код, подумаем...
PS Кстати, в твоем случае, логично воспользоваться волной, т.к. я понял, что веса всех ребер = 1.

Именно так. Весовые характеристики одинаковы.
По аоводу волного решения таже думал.
Но надо еще что бы был наиболее быстрый метод, и жрал по меньше ресурсов.
А то для каждой ветви приходится создавать новый динамический массив.
А Дийкстру я отсеял уже.
Надо что то новое.
Так как не все алгоритмы подхолят для большого количества узлов и не древовидной структуры.

Мысль:
-Построить граф вершин, достижимых из исходной. Здесь все вершины обходятся по 1 разу (может даже далеко не все в графе).
-Если цель туда попала=> пускать в нем волну (анализ уже не столь большого графа).
Должно неплохо работать для слабо связных графов...

Вообще то, кстати, у волны - трудоемкость О(n) - самая маленькая из всех...

Идейка интересная, надо будет попробовать. ;D ;D ;D
Но проблема опять таки в том, что структура графа довольно сложна.

Если число компонентов связности велико, то имеет смысл заводить не один граф, а сразу вектор указателей на графы. После этого, каждая точка должна знать свой граф => поиск упрощается.

Сейчас реализовал следующим образом
1. С начала проходит полный анализ графа с выявлением более простых структур, цикличностей и замкнутых областей.
2. Определяются точки перехода от одной структуры к другой. И множество всех точек в каждой структуре.
3. Внутри структур определяются точки развлетвления.
4. Определяются пути от каждой точки внутри структур.
5. Далее происходит поиск пути от точки к точке.

Как уже понятно все проблема именно в разделении на структуры, и поиск пути внутри них. Точнее не столько проблема, сколько огромное время тратится на это.

Вообще поиск компонент связности, блоков, мостов, точек сочленения, базы циклов и т.д. - это все классические алгоритмы. Приведены в любой нормальной книге (например Харари).
Кстати еще есть по-моему алгоритм Уоршалла, который по матрице смежности строит матрицу достижимости для графа. Однако, там по моему, высокая трудоемкость...., но точно не помню.
Ну ладно, успеха тебе. Если накопаешь чего интересного, пришли на мыло плиз. ;D
Графы меня всегда интересовали.

Обязательно ;D ;D ;D