Определение кратчайшего пути

Старая форма входа

Страница 1 из 1 1
Модератор форума: китин, _Boroda_

Мир MS Excel » Вопросы и решения » Вопросы по VBA » Определение кратчайшего пути (Макросы/Sub)

ВасилисаЛукьянчикова

Дата: Четверг, 20.12.2018, 21:18 | Сообщение № 1

Группа: Пользователи

Ранг: Участник

Сообщений: 64

Репутация: 0 ±

Замечаний: 0% ±

Excel 2016

Здравствуйте форумчане.
Помогите найти пункты кратчайшего пути.
На листе несколько фигур. Между некоторыми стоят отрезки.
Есть начальная фигура и конечная фигура.

Подскажите - как определить наикратчайший путь между фигурами и вывести названия объектов-узлов в таблицу Q9:Q21 ?

К сообщению приложен файл: 234234.xls (76.5 Kb)

Ответить

Roman777

Дата: Пятница, 21.12.2018, 06:54 | Сообщение № 2

Группа: Проверенные

Ранг: Ветеран

Сообщений: 980

Репутация: 127 ±

Замечаний: 0% ±

Excel 2007, Excel 2013

ВасилисаЛукьянчикова, Задача не особо похожа под эксель. Вам нужно найти кратчайшее расстояние, учитывая все кружки, или только те, между которыми есть отрезки? Похоже, что тут в любом случае только перебор. Но для начала необходимо отобрать те "отрезки", которые должны учитываться.

Много чего не знаю!!!!

Ответить

ВасилисаЛукьянчикова

Дата: Пятница, 21.12.2018, 08:03 | Сообщение № 3

Группа: Пользователи

Ранг: Участник

Сообщений: 64

Репутация: 0 ±

Замечаний: 0% ±

Excel 2016

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

Забыла указать дополнительные таблицы U9:W21 (координаты концов отрезков) и Y9:AA21 (координаты всех фигур).
С их помощью наверное можно как-то определить - какой отрезок какие фигуры связывает.

К сообщению приложен файл: 8231.xls (78.5 Kb)

Сообщение отредактировал ВасилисаЛукьянчикова - Пятница, 21.12.2018, 08:04

Ответить

MCH

Дата: Пятница, 21.12.2018, 08:56 | Сообщение № 4

Группа: Админы

Ранг: Старожил

Сообщений: 2003

Репутация: 751 ±

Замечаний: ±

Можно использовать алгоритм Дейкстры (или алгоритм Левита или алгоритм Форда-Беллмана) для поиска кратчайшего пути в графе
http://www.excelworld.ru/forum/3-6656-1

Ответить

ВасилисаЛукьянчикова

Дата: Пятница, 21.12.2018, 14:57 | Сообщение № 5

Группа: Пользователи

Ранг: Участник

Сообщений: 64

Репутация: 0 ±

Замечаний: 0% ±

Excel 2016

MCH, а как использовать этот алгоритм - для решения моей задачи ?

Ответить

MCH

Дата: Пятница, 21.12.2018, 15:56 | Сообщение № 6

Группа: Админы

Ранг: Старожил

Сообщений: 2003

Репутация: 751 ±

Замечаний: ±

примерно так

К сообщению приложен файл: 7673884.xlsb (34.7 Kb)

Ответить

ВасилисаЛукьянчикова

Дата: Пятница, 21.12.2018, 16:06 | Сообщение № 7

Группа: Пользователи

Ранг: Участник

Сообщений: 64

Репутация: 0 ±

Замечаний: 0% ±

Excel 2016

MCH, понятно буду разбираться.
Вроде бы - работает.
Спасибо за ответ.

Ответить

Ильнур_1990

Дата: Вторник, 15.01.2019, 19:11 | Сообщение № 8

Группа: Пользователи

Ранг: Прохожий

Сообщений: 3

Репутация: 0 ±

Замечаний: 0% ±

Excel 2016

MCH, здравствуйте! Подскажите, пожалуйста, на примере ВасилисыЛукьянчиковой (файл 8231.xls), как вы перегнали координаты вершин и графы с расстояниями в свой файл (7673884.xlsb)? Не может ведь быть, что вручную?

Ответить

MCH

Дата: Среда, 16.01.2019, 10:04 | Сообщение № 9

Группа: Админы

Ранг: Старожил

Сообщений: 2003

Репутация: 751 ±

Замечаний: ±

Цитата Ильнур_1990, 15.01.2019 в 19:11, в сообщении № 8 ()

как вы перегнали координаты вершин и графы с расстояниями в свой файл

Вершин всего 12, координаты их указаны
Ребер 10 (плюс 10 обратных), какие они вершины соединяют поставил вручную
Расстояния рассчитываются по формуле (Пифагора)