Графы (3d), c#, кратчайший путь. шаг за шагом

@legi · Регистрация: 24.09.2009

Студворк — интернет-сервис помощи студентам

Здравствуйте, уважаемые форумчане!
Передо мной стоит задача написать программу которая будет искать кратчайший путь по графу который визуально будет "3х-мерным", при этом как я понимаю, с точки зрения теории графов, это будет обычный граф, просто у некоторых узлов будет несколько "связей".

Я понимаю, что в инете эта тема обсосана со всех сторон, но мой мозг устроен так, что пока сам руками не сделаю, нифига в алгоритм не въеду

, и тем более не смогу правильно его запрограммировать.

Визуальную часть пишу на WPF. Она уже почти готова, скоро выложу тут.

Вообщем хотелось бы узнать, на этом форуме есть гуру, которые помогут мне шаг за шагом написать этот алгоритм?

В данный момент код хранения узлов графа выглядит так:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
    public class Node
    {
        public String Id; // id ноды
        public Point3D Coords; // её координаты в 3х мерном пространстве
        public List<Node> Connections = new List<Node>(); // массив для хранения взаимосвязей
    }
 
    public void InitGraph()
    {
        // делаю узел
        Node node0 = new Node();
        node0.Coords = new Point3D(0, 0, 0);
        node0.Id = "0-0-0";
 
        // второй узел
        Node node1 = new Node();
        node1.Coords = new Point3D(1, 0, 0);
        node1.Id = "1-0-0";
 
        //создаю взаимосвязи между ними
        node0.Connections.Add(node1);
        node1.Connections.Add(node0);
 
        // проверяю через дебагер, что в Connections хранится ссылка на объект
        // а не его копия
        node0.Id = "0-0-0-changed"; 
    }

На данном этапе уже есть два вопроса:

1. Как правильнее организовать взаимосвязь Node0<>Node1?
Ведь путь можно будет искать как начиная с Node0, так и с Node1

2. Надо ли на этапе "проектирования" добавлять поле(Boolean?), в котором будет хранится состояние того, что на этапе нахождения пути, мы уже были в этом узле?
Просто когда знакомился с алгоритмами, вроде как-то помечали ноду, что в ней уже были.

Добавлено через 1 час 46 минут

вот такой вот граф надо использовать. нарисовал, чтобы лучше продемонстрировать какие нужны взаимосвязи т.п.

Добавлено через 11 минут
для примера вот надо добраться из "0 1 1" в "3 0 2"

@solar_wind · 21.10.2009, 14:35

Мне кажется будет проще и нагляднее составить матрицу связей с размерностью зависящей от количество узлов графа.
А дальше по этой матрице остается отыскать кратчайший путь.
Кстати сталкивался с методами, которые позволяют решать такие, и даже более сложные, задачи. Поищи методы решения "Транспортных задач".
Или можно все решить обычным перебором вариантов. Промежуточные узлы, в которых уже были отмечать нужно, иначе будет зацикливание!

@legi · 21.10.2009, 14:55 **[ТС]**

как я понимаю, матрица - это более оптимизированная версия поиска пути?
я вот хотел бы сначала в лоб решить задачу, методом перебора.

т.е. найти путь с 0 1 1 до 3 0 2

как вот лучше хранить взаимосвязь между 0 0 0 и 1 0 0. Ведь если стартовая точка будет 1 0 0 то мы должны при методе перебора сходить до 0 0 0 так и до 2 0 0. но при этом если стартовая точка будет 0 0 0 , то мы должны иметь связь в сторону 1 0 0, так и 0 1 0 .

нормально ли является такой метод описания взаимосвязей:

C#
1
2
3
4
        
        //создаю взаимосвязи между ними
        node0.Connections.Add(node1);
        node1.Connections.Add(node0);

или есть более оптимальный?

@solar_wind · 21.10.2009, 15:08

Вообще координаты узлов это только для отображения, для задачи они не имеют вообще смысла. Есть какие то узлы, между некоторыми из них существует связь.
Например есть три узла, первый связан со вторым и третьим, матрица будет такой:
1 1 1
1 1 0
1 0 1

Тот метод описания взаимосвязей мне кажется слишком сложный для данной задачи.

@legi · 21.10.2009, 15:39 **[ТС]**

вот "сконвертировал" в 2d граф

и пронумеровал вершины. матрица должна быть 10*10?
такая?

и как по матрице искать?

@odip · 21.10.2009, 20:51

Вот твой алгоритм
http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
Алгори́тм Де́йкстры — алгоритм на графах, изобретенный Э. Дейкстрой. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Известен также под названием кратчайший путь — первый (Shortest Path First).

@legi · 21.10.2009, 21:18 **[ТС]**

там приведен в пример граф, у которого есть "цена" до следующей ноды, а что делать если цена одинакова?

@Mike · 21.10.2009, 22:41

посмотрите алгоритм флойда, реализуется намного проще чем дейкстры, да и для понимания прост:
всего лишь тройной фор(for).

@legi · 22.10.2009, 11:46 **[ТС]**

У Флойда вроде доже играет роль цена... Может с кем-то можно тут step-by-step сделать алгоритм для моего графа?
Вот вопрос созрел:
1) в матрице взаимосвязей хранить надо просто взаимосвязь, или ссылки(ref) на ноды, в которых .visited=false;
2) подобного рода матрицы являются универсальным инструментом? всеобщей практикой?

22.10.2009, 19:31

legi, ты матрицу по графу не совсем верно составил.
У тебя в графе нет петель, а следовательно узловые точки = 0.

1 2 3 ...
1 0 1 0...
2 1 0 1...
.......

И если у ребер цена одинаковая, то алгоритм тоже работает, ты просто задай цену = 1

@legi · 22.10.2009, 19:59 **[ТС]**

да, я исправил уже.

Вот я нашел код на С для алгоритма Лойда (http://snippets.dzone.com/posts/show/4759) и адаптировал его на c#. в конце вижу верно посчитанную матрицу. Цена верна, но как мне "проложить" путь от одного узла к другому?

@legi · 22.10.2009, 22:03 **[ТС]**

Тут ( <ссылка на форум> ) нашел Лойда на паскале. откомпилировал и вижу такую картину:
http://pic.ipicture.ru/uploads... gk2ISQ.png

что такое матрица путей и как ею пользоваться?
почему в матрице "длина дуг" длины дуг = 0?

Т.е. у меня задача найти коротки путь и потом пройтись по нему.

@legi · 23.10.2009, 03:37 **[ТС]**

Родил

Вроде работает, но блин опять пошёл методом "найти исходник и оттачить его напильником"

Теперь надо въехать в алгоритм. У кого нить есть человеческое (не математическое) описание его(Флойда)?

@legi · 02.11.2009, 02:16 **[ТС]**

FloydWarshall.rar - исходники и exe программа для поиска пути в графе по Алгоритму Флойда — Уоршелла и так же строит матрицу по которой можно построить путь (программа строит путь) из одного узла к другому. Проект на C# Microsоft Visual Studio 2008

graf.zip - программа для визуализации графов (без исходников) от Беднова Александр Викторовича (DarkShurik@mail.ru) , откопал где-то на фриварных файлохранилищах (http://freesoft.ru/?author=1072).

@freegat · 02.11.2009, 19:08

У меня возник вопрос после прочтения темы практического характера:
как в реальных условиях алгоритм "заточен" и действует?!?
То есть: как определить расстояние от базы экстренной службы до места вызова!??
как выбирается вершины графа и растояния между ними на местности и карте??!

@galileopro · 02.11.2009, 19:48

Строишь граф. Вібираешь 2 вершині. И по алгоритму находишь минимальный путь между ними.

Добавлено через 4 минуты
Вот есть карта. На ней города. Каждый город - вершина графа. Ну а от акого города в какой тебе надо попасть, это уже тебе решать.

@freegat · 03.11.2009, 04:42

Сообщение от galileopro

Строишь граф. Вібираешь 2 вершині. И по алгоритму находишь минимальный путь между ними.

Добавлено через 4 минуты
Вот есть карта. На ней города. Каждый город - вершина графа. Ну а от акого города в какой тебе надо попасть, это уже тебе решать.

Нет, я имел немного другое ввиду: не много городов, а один огромный МЕГАПОЛИС....И нужно по кротчайшему пути попасть из одного конца города в другой. Как при этом выбираются вершины графа, связываясь с реальной картой города?!?

@legi · 03.11.2009, 13:02 **[ТС]**

freegat, именно этот (флойда-уоршелла) алгоритм не подойдет тут (жрёт время/память/элементарный).
насколько тут подойдет дейсктра - не знаю

и то, она должна быть модифицированная, т.е. быть быстрой - и учитывать одностороннее движение.

а так: пересечения улиц - это узлы графа. длину/цену (в данном случае это время езды при 60 км/ч) графа можно подсчитать при формировании графа. т.к. у нас есть реальные координаты пересечений, то мы можем вычислить реальные расстояния, а на основе них - "цену"("вес" в математической терминологии).

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

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@solar_wind 770 / 760 / 59 Регистрация: 06.07.2009 Сообщений: 3,021
	21.10.2009, 14:35
	Мне кажется будет проще и нагляднее составить матрицу связей с размерностью зависящей от количество узлов графа. А дальше по этой матрице остается отыскать кратчайший путь. Кстати сталкивался с методами, которые позволяют решать такие, и даже более сложные, задачи. Поищи методы решения "Транспортных задач". Или можно все решить обычным перебором вариантов. Промежуточные узлы, в которых уже были отмечать нужно, иначе будет зацикливание! 0

@solar_wind 770 / 760 / 59 Регистрация: 06.07.2009 Сообщений: 3,021
	21.10.2009, 15:08
	Вообще координаты узлов это только для отображения, для задачи они не имеют вообще смысла. Есть какие то узлы, между некоторыми из них существует связь. Например есть три узла, первый связан со вторым и третьим, матрица будет такой: 1 1 1 1 1 0 1 0 1 Тот метод описания взаимосвязей мне кажется слишком сложный для данной задачи. 0

@legi 0 / 0 / 0 Регистрация: 24.09.2009 Сообщений: 14
	21.10.2009, 15:39 [ТС]
	вот "сконвертировал" в 2d граф и пронумеровал вершины. матрица должна быть 10*10? такая? и как по матрице искать? 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	21.10.2009, 20:51
	Вот твой алгоритм http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры Алгори́тм Де́йкстры — алгоритм на графах, изобретенный Э. Дейкстрой. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Известен также под названием кратчайший путь — первый (Shortest Path First). 0

@legi 0 / 0 / 0 Регистрация: 24.09.2009 Сообщений: 14
	21.10.2009, 21:18 [ТС]
	там приведен в пример граф, у которого есть "цена" до следующей ноды, а что делать если цена одинакова? 0

@Mike 18 / 18 / 2 Регистрация: 20.01.2009 Сообщений: 71
	21.10.2009, 22:41
	посмотрите алгоритм флойда, реализуется намного проще чем дейкстры, да и для понимания прост: всего лишь тройной фор(for). 0

@legi 0 / 0 / 0 Регистрация: 24.09.2009 Сообщений: 14
	22.10.2009, 11:46 [ТС]
	У Флойда вроде доже играет роль цена... Может с кем-то можно тут step-by-step сделать алгоритм для моего графа? Вот вопрос созрел: 1) в матрице взаимосвязей хранить надо просто взаимосвязь, или ссылки(ref) на ноды, в которых .visited=false; 2) подобного рода матрицы являются универсальным инструментом? всеобщей практикой? 0

zaqxsw
	22.10.2009, 19:31
	legi, ты матрицу по графу не совсем верно составил. У тебя в графе нет петель, а следовательно узловые точки = 0. 1 2 3 ... 1 0 1 0... 2 1 0 1... ....... И если у ребер цена одинаковая, то алгоритм тоже работает, ты просто задай цену = 1

@legi 0 / 0 / 0 Регистрация: 24.09.2009 Сообщений: 14
	22.10.2009, 19:59 [ТС]
	да, я исправил уже. Вот я нашел код на С для алгоритма Лойда (http://snippets.dzone.com/posts/show/4759) и адаптировал его на c#. в конце вижу верно посчитанную матрицу. Цена верна, но как мне "проложить" путь от одного узла к другому? 0

@legi 0 / 0 / 0 Регистрация: 24.09.2009 Сообщений: 14
	22.10.2009, 22:03 [ТС]
	Тут ( <ссылка на форум> ) нашел Лойда на паскале. откомпилировал и вижу такую картину: http://pic.ipicture.ru/uploads... gk2ISQ.png что такое матрица путей и как ею пользоваться? почему в матрице "длина дуг" длины дуг = 0? Т.е. у меня задача найти коротки путь и потом пройтись по нему. 0

@legi 0 / 0 / 0 Регистрация: 24.09.2009 Сообщений: 14
	23.10.2009, 03:37 [ТС]
	Родил Вроде работает, но блин опять пошёл методом "найти исходник и оттачить его напильником" Теперь надо въехать в алгоритм. У кого нить есть человеческое (не математическое) описание его(Флойда)? 0

@freegat 23 / 23 / 5 Регистрация: 05.03.2009 Сообщений: 181
	02.11.2009, 19:08
	У меня возник вопрос после прочтения темы практического характера: как в реальных условиях алгоритм "заточен" и действует?!? То есть: как определить расстояние от базы экстренной службы до места вызова!?? как выбирается вершины графа и растояния между ними на местности и карте??! 0

@galileopro Пробующий 185 / 98 / 10 Регистрация: 28.04.2009 Сообщений: 1,101
	02.11.2009, 19:48
	Строишь граф. Вібираешь 2 вершині. И по алгоритму находишь минимальный путь между ними. Добавлено через 4 минуты Вот есть карта. На ней города. Каждый город - вершина графа. Ну а от акого города в какой тебе надо попасть, это уже тебе решать. 0

@legi 0 / 0 / 0 Регистрация: 24.09.2009 Сообщений: 14
	03.11.2009, 13:02 [ТС]
	freegat, именно этот (флойда-уоршелла) алгоритм не подойдет тут (жрёт время/память/элементарный). насколько тут подойдет дейсктра - не знаю и то, она должна быть модифицированная, т.е. быть быстрой - и учитывать одностороннее движение. а так: пересечения улиц - это узлы графа. длину/цену (в данном случае это время езды при 60 км/ч) графа можно подсчитать при формировании графа. т.к. у нас есть реальные координаты пересечений, то мы можем вычислить реальные расстояния, а на основе них - "цену"("вес" в математической терминологии). при этом, думаю, если надо начинать считать путь не с пересечения, а с середины улицы (а это уже node(забыл как по русски)) то, node-надо делить на две части, и делать виртуальный узел. как это действительно реализовано в ГИС-ах, остается догадываться 0