Поиск кратчайшего пути по алгоритму Флойда-Уоршелла

Публикация № 442306

Разработка - Практика программирования

Поиск пути алгоритм Флойд Уоршелл

16
Поиск кратчайшего пути между точками (складами) по алгоритму Флойда-Уоршелла

Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом (англ.), хотя в 1959году Бернард Рой (англ.) (Bernard Roy) опубликовал практически такой же алгоритм, но это осталось незамеченным.


Обработка содержит функцию расчета пути и пример вызова.

В функцию передаётся начальная точка, конечная точка и таблица значений содержащая маршруты между точками с расстоянием между ними.

Таблица значений маршрутов должна содержать 3 колонки: "СкладОткуда", "СкладКуда" и "Расстояние".

Функция возвращает значение "Неопределено" (если нет пути) или строки из исходной таблицы значений (с маршрутами) по которым проложен путь.


Пример использования :

тзМаршруты = Новый ТаблицаЗначений;
тзМаршруты.Колонки.Добавить("СкладОткуда");
тзМаршруты.Колонки.Добавить("СкладКуда");
тзМаршруты.Колонки.Добавить("Расстояние");

ДобавитьЗапись(тзМаршруты, "Склад1", "Склад2", 1);
ДобавитьЗапись(тзМаршруты, "Склад1", "Склад3", 2);
ДобавитьЗапись(тзМаршруты, "Склад1", "Склад4", 3);
ДобавитьЗапись(тзМаршруты, "Склад3", "Склад2", 4);
ДобавитьЗапись(тзМаршруты, "Склад4", "Склад3", 5);
ДобавитьЗапись(тзМаршруты, "Склад4", "Склад5", 6);
СкладОткуда = "Склад1";
СкладКуда = "Склад5";

тзПути = КратчайшийПутьПоФлойду(СкладОткуда, СкладКуда, тзМаршруты);
Если тзПути<>Неопределено Тогда
  Сообщить("Минимальный путь: "+тзПути.Итог("Расстояние"));
  Сообщить("Найденные маршруты:");
  Для Каждого ТекМаршрут Из  тзПути Цикл
    Сообщить(""+ТекМаршрут .СкладОткуда+" - "+ТекМаршрут.СкладКуда+"-"+ТекМаршрут.Расстояние);
  КонецЦикла;
КонецЕсли;
16

Скачать файлы

Наименование Файл Версия Размер
FindFloid
.epf 7,62Kb
09.01.16
24
.epf 1.0 7,62Kb 24 Скачать

Специальные предложения

Комментарии
Избранное Подписка Сортировка: Древо
1. dablack 09.01.16 12:49 Сейчас в теме
Таблицу в которой около 40 "складов" (не строк) обработает ? пробовали ?
2. Garykom 16 09.01.16 14:22 Сейчас в теме
(1) dablack,
нет не пробовал, скиньте пример такой таблицы, попробую и выложу результат
но до 1000 складов нормально должно работать
3. dablack 10.01.16 17:08 Сейчас в теме
Вот файл таблицы значений через ЗначениеВФайл. Таблица из 32 пунктов.
Попробуйте пожалуйста.
Прикрепленные файлы:
dist.tz
4. Garykom 16 11.01.16 13:56 Сейчас в теме
(3) dablack, все пути из Склад1 в (Склад2 - Склад32) в один шаг самые короткие

P.S. хотя ошибаюсь, сразу не заметил что вместо прямого Склад1 - Склад20 = 310 395

Начали расчет: 11.01.2016 13:51:46 Склад1 - Склад20
Окончили расчет: 11.01.2016 13:51:47 Склад1 - Склад20
Минимальный путь: 310 394
|СкладОткуда|СкладКуда|Расстояние
|Склад1|Склад27|243 052
|Склад27|Склад20|67 342

на 1 меньше ))
Прикрепленные файлы:
32 склада.txt
5. Garykom 16 03.02.16 20:07 Сейчас в теме
Кому интересно есть продвинутая версия.
Которая умеет считать маршруты когда они не постоянные статичные.
А разные (периодические) по разным по дням недели.
6. ildarovich 6770 04.02.16 13:37 Сейчас в теме
Попытался сравнить быстродействие приведенного здесь метода с методом из статьи Определение кратчайших путей, критических путей одним запросом. . По идее, алгоритм Флойда должен иметь сравнимое быстродействие. Его оценка трудоемкости ~O(N^3), метода "матричного умножения" ~O(Log(K)*N^3), где К - диаметр графа. Множитель Log(K) нивелируется тем, что массовые вычисления в запросе делаются "пакетом" и поэтому быстрее в 10-50 раз.
Однако столкнулся с тем, что на схеме метро функция не работает. Насколько я понял, отрезки пути, найденные алгоритмом, не находятся в исходном графе.
Прилагаю файл связности станций питерского метро, полученный сохранением в текстовом файле строки, равной ЗначениеВСтрокуВнутр(ТаблицаМаршрутов).
Прикрепленные файлы:
МетроПитер.txt
7. Garykom 16 08.02.16 11:20 Сейчас в теме
(6) ildarovich, боюсь некорректно сравнивать эти два метода.
Флойд долго думает, но считает сразу одновременно все длины и находит кратчайшие пути между всеми парами вершин.
Т.е. после расчета и сохранения в массивы результат выдается мгновенно для любой пары вершин.
8. ildarovich 6770 08.02.16 12:13 Сейчас в теме
(7) думаю, вы невнимательно прочитали статью, на которую я неоднократно ссылался. Это метод, решающий ту же задачу "All Pairs Shortest Paths (APSP) problem". Так же находятся кратчайшие расстояния между всеми парами вершин. Поэтому сравнивать эти решения можно и нужно.

Проблема в том, что практическая реализация метода, сделанная здесь, пока, на мой взгляд, попросту НЕ РАБОТАЕТ. Вообще не находит путь в графе, пример которого приведен в (6) (вываливается с ошибкой).

Кстати, проблема восстановления кратчайшего пути по кратчайшим расстояниям между всеми парами в статье решается гораздо проще. В кратчайший путь включаются все вершины ПунктПути, обладающие свойством:
КратчайшееРасстояние(Откуда, ПунктПути) + КратчайшееРасстояние(ПунктПути, Куда) = КратчайшееРасстояние(Откуда, Куда)
Пункты упорядочиваются по КратчайшееРасстояние(Откуда, ПунктПути). При этом никаких предыдущих вершин вычислять и хранить вообще не нужно. Дополнительно это дает возможность вывода нескольких равнозначных вариантов равной длины. Затраты на проверку лишних вершин, которые потом не войдут путь, очень малы (по отношению к основным затратам метода).
9. ildarovich 6770 08.02.16 16:15 Сейчас в теме
+(6) файлы схемы метро в другом формате (mxl, xls)
Прикрепленные файлы:
МетроПитер.mxl
МетроПитер.xls
МетроМосква.mxl
10. Garykom 16 08.02.16 16:25 Сейчас в теме
(9) ildarovich, все работает

Маршрут считает, что по дням - это с другого более сложного проекта :)

Считал 15 минут потому что 140 станций * 7 дней вершин
Прикрепленные файлы:
11. ildarovich 6770 08.02.16 18:25 Сейчас в теме
(10) я взял функцию из вашей обработки, вставил в свою, получил ошибку (см.скриншоты). - Что я делаю не так?

Отладчик показал, что отрезок пути, который ищется в ТЗМаршруты, там не находится, из-за этого ТекСтр = Неопределено и функция вылетает.

Кстати, создавать колонку поиска было необязательно, достаточно было проиндексировать ТЗ по двум колонкам: тзМаршруты.Индексы.Добавить("СкладОткуда, СкладКуда").

Про
потому что 140 станций * 7 дней вершин
не понял. В Питере ~65 станций. 140 - это число связей между станциями.

В общем, хотелось бы разобраться и получить результат сравнения по скорости, не отлаживая самому вашу разработку.
Прикрепленные файлы:
12. Garykom 16 08.02.16 18:46 Сейчас в теме
(11) ildarovich, проверял на доработанном алгоритме который умеет считать маршруты между складами когда они не по каждым дням недели ездят.
Причем с ожиданием если в этот день недели когда приехали нет маршрутов отправления.
для простоты проверил на доработанном, там из екселя как раз загрузка идет, при расчете он каждую вершину (склад, станцию) превращает в 7 по количеству дней в неделе, и даты которые показывает это сколько дней едем
и да ошибся не 140*7, а 65*7

насчет ошибки все правильно, восстановление пути для Флойда возможно двумя способами :) http://hci.fenster.name/304y/lab5/
в выложенном сделан "...В этом случае значение массива C[j][k] после окончания алгоритма будет указывать одну из вершин, через которую проходит путь от j к k ..."
выложенный алгоритм правильно считает кратчайший путь, но не всегда может его восстановить
13. ildarovich 6770 09.02.16 21:40 Сейчас в теме
(12) в общем, пришлось свою реализацию сделать. Вот что получилось у меня:
Функция КратчайшийПутьФлойд(Откуда, Куда, Дуги) Экспорт
	// загрузка графа в "соответствие соответствий" так, что Пути[Откуда][Куда] = Длина
	Пути = Новый Соответствие;
	Для каждого Дуга Из Дуги Цикл
		Пути[Дуга.Откуда] = ?(Пути[Дуга.Откуда] = Неопределено, Новый Соответствие, Пути[Дуга.Откуда]);
		Пути[Дуга.Откуда][Дуга.Куда] = Дуга.Длина
	КонецЦикла;
	// три вложенных цикла по узлам графа
	Для каждого Узел1 Из Пути Цикл // тогда Узел.Ключ - это одна вершина из полного множества вершин  
		Для каждого Узел2 Из Пути Цикл 
			Если Пути[Узел2.Ключ][Узел1.Ключ] <> Неопределено Тогда
				Для каждого Узел3 Из Узел1.Значение Цикл // здесь только вершины, связанные с Узел1.Ключ 
					Длина = Пути[Узел2.Ключ][Узел3.Ключ];
					Обход = Пути[Узел2.Ключ][Узел1.Ключ] + Узел3.Значение; // Узел3.Значение == Пути[Узел1.Ключ][Узел3.Ключ]
					Пути[Узел2.Ключ][Узел3.Ключ] = ?(Длина = Неопределено, Обход, Мин(Длина, Обход))
				КонецЦикла 
			КонецЕсли 
		КонецЦикла 
	КонецЦикла;
	// восстановление пути
	Путь = Дуги.СкопироватьКолонки("Куда, Длина");
	Путь.Добавить().Куда = Откуда;
	Путь.Добавить().Куда = Куда;
	Путь[1].Длина = Пути[Откуда][Куда];
	Для каждого Узел Из Пути Цикл 
		Если Пути[Откуда][Узел.Ключ] <> Неопределено И Пути[Узел.Ключ][Куда] <> Неопределено 
			И Пути[Откуда][Узел.Ключ] + Пути[Узел.Ключ][Куда] = Пути[Откуда][Куда] Тогда
			ЗаполнитьЗначенияСвойств(Путь.Добавить(), Новый Структура("Куда, Длина", Узел.Ключ, Пути[Откуда][Узел.Ключ]))
		КонецЕсли
	КонецЦикла;
	Путь.Сортировать("Длина");
	Возврат Путь
КонецФункции // КратчайшийПуть()
Показать
На примере московского метро примерно на 30% быстрее запроса получается.
По ходу дела нашел на ИС статью на смежную тему: Реализация алгоритма Дейкстры. В статье также заявлена и реализация Флойда.

... Ну и еще. Поскольку массив работает быстрее соответствия, попробовал, как и автор, на всякий случай вариант с массивом:
Функция КратчайшийПуть(Откуда, Куда, Дуги) Экспорт
	// нумерация вершин
	Номер = Новый Соответствие;
	Номер[Откуда] = 0;
	Номер[Куда  ] = 1; // Если Откуда = Куда Тогда Возврат Новый ТаблицаЗначений КонецЕсли; 
	Для каждого Дуга Из Дуги Цикл
		Номер[Дуга.Откуда] = ?(Номер[Дуга.Откуда] = Неопределено, Номер.Количество(), Номер[Дуга.Откуда]);
		Номер[Дуга.Куда  ] = ?(Номер[Дуга.Куда  ] = Неопределено, Номер.Количество(), Номер[Дуга.Куда  ])
	КонецЦикла;                                                                      
	// инициализация массива-матрицы инцидентности
	ВГраница = Номер.Количество() - 1;
	Пути = Новый Массив(ВГраница + 1, ВГраница + 1);
	Много = 999999999;
	Для ё = 0 По ВГраница Цикл
		Для ж = 0 По ВГраница Цикл
			Пути[ё][ж] = ?(ё = ж, 0, Много) 
		КонецЦикла 
	КонецЦикла; 
	// загрузка графа в массив
	Для каждого Дуга Из Дуги Цикл
		Пути[Номер[Дуга.Откуда]][Номер[Дуга.Куда]] = Дуга.Длина
	КонецЦикла;
	// тело алгоритма Флойда-Уоршолла
	Для к = 0 По ВГраница Цикл
		Для ё = 0 По ВГраница Цикл
			Для ж = 0 По ВГраница Цикл
				Пути[ё][ж] = Мин(Пути[ё][ж], Пути[ё][к] + Пути[к][ж]) 
			КонецЦикла                                                                       
		КонецЦикла 
	КонецЦикла;
	// восстановление пути
	Путь = Дуги.СкопироватьКолонки("Куда, Длина");
	Для каждого Элемент Из Номер Цикл 
		Если Пути[0][Элемент.Значение] + Пути[Элемент.Значение][1] = Пути[0][1] Тогда
			ЗаполнитьЗначенияСвойств(Путь.Добавить(), Новый Структура("Куда, Длина", Элемент.Ключ, Пути[0][Элемент.Значение]))
		КонецЕсли
	КонецЦикла;
	Путь.Сортировать("Длина");
	Возврат Путь
КонецФункции // КратчайшийПуть()                                                           
Показать
Но получилось медленнее (в два раза к запросу)! Наверное, из-за экономия на переборе во вложенном цикле, где при использовании соответствия учитываются только существующие на данной итерации связи. В итоге для большой реальной задачи все же рекомендую использовать вариант с соответствием. Он на данный момент самый быстрый, да и кода там меньше.
14. Garykom 16 11.02.16 13:31 Сейчас в теме
(13) ildarovich, на 30% быстрее получилось потому что соединили алгоритмы Флойда и Дейкстры.
И еще потому что вершин и ребер мало. Особенно потому что количество ребер практически равно количеству вершин - линии метро однако.

Попробуйте на 500 вершинах и 5000 ребер? Запрос в этом случае умрет, вариант с соответствием будем в 2-2.5 раза медленнее чем с массивами. Точно будет зависеть от отношения количества вершин к количеству ребер.
15. ildarovich 6770 11.02.16 14:39 Сейчас в теме
(14)
Запрос в этом случае умрет, вариант с соответствием будем в 2-2.5 раза медленнее чем с массивами
- А ставку сделать готовы?
соединили алгоритмы Флойда и Дейкстры
Это не так. В алгоритме Дейкстры требуется минимум в неразвитых ветвях искать. Здесь поиска минимума и развития ветвей нет.
16. Garykom 16 12.02.16 10:40 Сейчас в теме
(15) ildarovich,
- А ставку сделать готовы?

Так по опыту собственному и сужу

Это не так. В алгоритме Дейкстры требуется минимум в неразвитых ветвях искать. Здесь поиска минимума и развития ветвей нет.

Какая разница каким образом оптимизировать алгоритм?
Алгоритм Дейкстры просматривает ребра (получая из них вершины), обычный Флойда все вершины парами (не важно есть ли между ними ребро).

Модернизированный Флойд:
"Но существует решение и за \sum_{n,\;n,\;n}O(1) = O(n^2), где хранятся значения не для всех вершин, а только значения для предыдущей вершины, так как следующая получается рекурсивно."
https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D­0%A4%D0%BB%D0%BE%D0%B9%D0%B4%D0%B0_%E2%80%94_%D0%A3%D0%BE%D1­%80%D1%88%D0%B5%D0%BB%D0%BB%D0%B0

И да через битовые маски еще быстрее...
17. ildarovich 6770 12.02.16 14:02 Сейчас в теме
(16)
- А ставку сделать готовы?
Я написал это, чтобы побудить вас поспорить на что-нибудь, чтобы мне было интереснее сравнительное тестирование провести. Задача я бы не сказал, чтобы популярная, поэтому пока не решил, стоит ли этим заниматься.
Статью в Википедии я и раньше видел, этот оборот (про N^2) не понял, честно говоря (источник там не указан). В английской версии этой фразы нет. Если вы поняли о чем там речь или знаете где можно про прочитать, подскажите.
Так что битовые маски не ЕЩЕ быстрее, а просто быстрее. Ну а так как битовых масок в 1С нет, то соответствие а последнем цикле и играет роль маски - позволяет не проверять не существующие дуги.
18. Garykom 16 12.02.16 17:46 Сейчас в теме
(17) ildarovich, понимаете мне это тестирование совершенно неинтересно.
Потому что прекрасно понимаю что при разных исходных данных будет разный результат.

Про N^2 это то что вы и сделали по сути.
Просто за счет "Если Пути[Узел2.Ключ][Узел1.Ключ] <> Неопределено Тогда" исключили из алгоритма обработку несуществующих ребер.
Если число ребер во много раз больше чем число вершин эта доработка за счет лишнего действия (проверка по условию в выниманием значения из структур и сравнение) даст замедление.

А битовые маски это то что и сделали (доп условие перед 3-м циклом) только проверка очень быстрая с помощью бинарных операций.
Бинарные операции в 1С реализуемы через числа и деление нацело с остатком (%).
http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A­4%D0%BB%D0%BE%D0%B9%D0%B4%D0%B0

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

ЗЗЫ еще тонкость с 1С, когда запускают тестирование из "конфигуратора через отладку", и напрямую запускают "режим предприятия"
в этом случае отладчик слегка портит результаты
Оставьте свое сообщение

См. также

Описание формата внутреннего представления данных 1С в контексте обмена данными 150

Статья Программист Внешняя обработка (ert,epf) v8 v8::УФ 1cv8.cf Абонемент ($m) Практика программирования Внешние источники данных Разработка

Фирма 1С не рекомендует использовать внутреннее представление данных для любых целей, которые отличны от обмена с 1С:Предприятием 7.7. Но сама возможность заглянуть на "внутреннюю кухню" платформы с помощью функций ЗначениеВСтрокуВнутр(), ЗначениеВФайл(), ЗначениеИзСтрокиВнутр() и ЗначениеИзФайла(), дала возможность сообществу программистов 1С разработать новые приемы разработки и анализа. Так, именно на использовании внутреннего представления был построен алгоритм "быстрого массива", который позволяет практически мгновенно создать массив в памяти на основании строки с разделителями. С помощью разбора внутреннего представления можно "на лету" программным кодом выполнить анализ обычной формы и даже сделать редактор графической схемы. Во внутреннем формате сохраняют свои данные между сеансами различные популярные внешние обработки. А еще это возможность сделать быстрый обмен с внешними системами.

1 стартмани

06.09.2019    5737    5    Dementor    27       

Вам нравятся запросы в 1С? 14

Инструменты и обработки Программист Конфигурация (md, cf) v8 v8::Запросы 1cv8.cf Абонемент ($m) Практика программирования Разработка

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

1 стартмани

03.07.2019    10647    1    m-rv    79       

1С:Ассемблер. Немного летнего веселья! 306

Статья Программист Внешняя обработка (ert,epf) v8 1cv8.cf Абонемент ($m) Практика программирования Разработка

Все вы, наверное, слышали, что 1С-ники жалуются на свою систему, считая язык 1С недостаточно низкоуровневым, скучным и т.п. Все они с тоской поглядывают в сторону "настоящих" языков программирования. Так вот, господа, они неправы. В системе 1С есть места, где можно размять программерский мозг и получить удовольствие от низкоуровневой техники. Предлагаю вам погрузиться в недра виртуальной машины 1С и понять, как она работает. Там есть свой "ассемблер" и мы попробуем его в действии!

1 стартмани

21.06.2019    15078    46    Evil Beaver    113       

Простые примеры сложных отчетов на СКД 263

Статья Программист Архив с данными v8 v8::СКД 1cv8.cf Абонемент ($m) Практика программирования

Подписи в отчете. Особенности соединения наборов: как соединить несоединяемое. Остатки на дату и обороты по месяцам в одном отчете. Курс валюты на каждую дату без группировок и соединений в запросе. Отчет с произвольными колонками и с произвольной последовательностью. "Неадекватный отчет".

1 стартмани

12.06.2019    14281    11    Hatson    22       

Безопасная работа с транзакциями во встроенном языке 187

Статья Программист Конфигурация (md, cf) v8 1cv8.cf Абонемент ($m) Практика программирования Разработка

Разбираемся с опасностями использования транзакций во встроенном языке 1С. Познаем ошибку "В данной транзакции уже происходили ошибки". Учимся защищаться от них.

1 стартмани

25.03.2019    15866    7    tormozit    35       

Баг или фича? Неожиданное поведение платформы 168

Статья Системный администратор Программист Конфигурация (md, cf) v8 1cv8.cf Абонемент ($m) Практика программирования Тестирование и исправление Разработка

Рассмотрим несколько случаев неожиданного поведения платформы 1С, а также что с этим можно cделать.

18.02.2019    13013    31    YPermitin    88       

Коннектор: удобный HTTP-клиент для 1С:Предприятие 8 548

Инструменты и обработки Программист Конфигурация (md, cf) v8 1cv8.cf Абонемент ($m) Практика программирования Внешние источники данных WEB Универсальные функции Инструментарий разработчика Универсальные обработки

Коннектор - библиотека для работы с HTTP запросами. Библиотека берет на себя всю рутину работы с HTTP запросами. Буквально в одну строку можно получать данные, отправлять, не заботясь о необходимости конструирования URL, кодирования данных и т.п.

1 стартмани

31.01.2019    28907    267    bonv    111       

HTML в новой версии 8.3.14 на примере 3-х JavaScript библиотек: AmCharts, HighCharts, DHTMLX 172

Статья Программист Внешняя обработка (ert,epf) v8 1cv8.cf Абонемент ($m) Универсальные обработки Практика программирования Разработка

Тестируем возможности HTML в новой версии 8.3.14 платформы на примере 3-х JavaScript библиотек: AmCharts, HighCharts, DHTMLX.

1 стартмани

29.01.2019    14584    66    Synoecium    37       

Отладка сложных отчетов на СКД 139

Отчеты и формы Программист Расширение (cfe) v8 v8::СКД 1cv8.cf Россия Абонемент ($m) Практика программирования

Расширение для отладки сложных отчетов на СКД (в т.ч. для собираемых программно "на лету") и быстрого перехода к отладке таких отчетов в консоли запросов и отчетов на СКД.

1 стартмани

28.12.2018    14817    58    maxx    56       

Реализация простого http-сервиса "Просмотр карточки номенклатуры(товара) в браузере" 144

Статья Программист Конфигурация (md, cf) v8 1cv8.cf Абонемент ($m) Практика программирования

Практический пример реализации простого http-сервиса средствами 1С Предприятие 8.3. Обеспечивает просмотр списка товаров и просмотр данных товара в браузере.

1 стартмани

07.12.2018    14106    10    dmitry1975    31       

Использование подсистемы БСП "Заполнение объектов" 135

Статья Программист Расширение (cfe) v8 v8::УФ 1cv8.cf Россия Абонемент ($m) Практика программирования Универсальные функции БСП (Библиотека стандартных подсистем)

Применение механизмов БСП для добавления новых команд заполнения к формам различных объектов. Использование расширений конфигурации для доработки. Шаблоны для реализации собственных команд заполнения.

1 стартмани

23.11.2018    14209    8    ids79    22       

Работа с публикациями "Инфостарт" 14

Инструменты и обработки Программист Архив с данными v8 УУ Абонемент ($m) Практика программирования О сообществе WEB

Работа с рублевыми публикациями на сайте "Инфостарт": ведение клиентов, заказов, обновление файлов публикации, рассылка обновлений.

1 стартмани

13.09.2018    9762    10    RocKeR_13    16       

HTTP Сервисы: Путь к своему сервису. Часть 3 134

Инструменты и обработки Системный администратор Программист Расширение (cfe) v8 1cv8.cf Абонемент ($m) Инструментарий разработчика Практика программирования

Продолжение статьи «HTTP Сервисы: Путь к своему сервису. Часть 2». В предыдущих частях мы использовали только Get, в этой части поговорим о других методах и длительных операциях.

1 стартмани

27.08.2018    17006    32    dsdred    13       

Позиционирование в помещении с помощью нейросети по сигналу Wi-Fi. Интерактивная карта склада в 1С с показом позиции 65

Инструменты и обработки Программист Бизнес-аналитик Приложение (apk) v8 Windows Абонемент ($m) Инструментарий разработчика Практика программирования

Данная публикация содержит в себе редактор и интерактивную карту склада или иного помещения, на которой в реальном времени отображается позиция устройства, координаты которого вычисляются по уровням сигнала нескольких роутеров Wi-Fi. В статье и приложенным к ней разработкам предлагаются инструменты и методика для реализации вычисления точной геопозиции внутри помещений с помощью нейронной сети. Конфигурация написана на релизе 1С:Предприятие 8.3.12.1412, клиентское приложение имеет минимальный уровень совместимости SDK -16.

5 стартмани

09.08.2018    16237    23    informa1555    26       

Работа с данными выбора 40

Инструменты и обработки Программист Архив с данными v8 Россия Абонемент ($m) Практика программирования Работа с интерфейсом

В управляемом интерфейсе заложена мощная возможность описывать связи реквизитов формы через параметры. Установка параметров связей позволяет ограничить выбор данных так, чтобы целостность данных была обеспечена на этапе ввода. Однако без дополнительного программирования задать можно только самые простые связи. Такие условия связи, как зависимость от реквизита через точку или зависимость через дополнительное отношение, заданное в регистре сведений - уже задать без программирования не получится.

1 стартмани

17.07.2018    22553    13    kalyaka    15       

HTTP Сервисы: Путь к своему сервису. Часть 1 274

Статья Системный администратор Программист Расширение (cfe) v8 1cv8.cf Абонемент ($m) Практика программирования WEB

Уже много было написано про http-сервисы, но то и дело всплывают «Новые» статьи по обмену между базами V8 по COM, что «Немножко» удивляет. Решил внести свои 5 копеек, поработаем с http-сервисом.

1 стартмани

15.07.2018    39620    16    dsdred    22       

ВСТАВИТЬ В Справочник.Номенклатура (Код, Наименование) ЗНАЧЕНИЯ ("001", "Новый товар") 105

Инструменты и обработки Программист Внешняя обработка (ert,epf) v8 v8::Запросы 1cv8.cf Абонемент ($m) Практика программирования

Вас не обманывают ваши глаза, это запрос на изменение данных! И это работает без прямого доступа к БД, регистрации и смс.

1 стартмани

01.06.2018    20239    86    m-rv    57       

БСП: Дополнительная обработка (Регламенты), примеры от простого к сложному 240

Статья Программист Внешняя обработка (ert,epf) v8 1cv8.cf Абонемент ($m) Практика программирования БСП (Библиотека стандартных подсистем)

Очень много попадается странных решений, которые можно решить через БСП:Дополнительные отчеты и обработки. Я бы вообще БСП из-за этой подсистемы переименовал в «Большое Спасибо Программистам». Поработаем с подсистемой в части написания регламентных заданий.

1 стартмани

10.05.2018    28215    28    dsdred    34       

Как выполнить отчет на СКД через COM и получить данные отчета? 86

Статья Программист Архив с данными v8 УПП1 Россия Windows Абонемент ($m) Практика программирования

Для чего это нужно. Например, нужно в одной базе получить какой-либо показатель из другой базы. Этот показатель вычисляется в каком-либо сложном отчете, который написан на СКД. Можно, конечно, "скопипастить" текст запроса из другой базы, немного подправить его и выполнять в том же COM подключении. Но с этим теряется гибкость: если отчет изменился, то нужно помнить о том, что где-то есть его "немного модифицированная" копия. В статье будет рассмотрен пример получения данных из базы ЗУП.

2 стартмани

08.05.2018    18365    10    wowik    3       

Работа со схемой запроса 176

Статья Программист Конфигурация (md, cf) v8 v8::Запросы Абонемент ($m) Инструментарий разработчика Практика программирования

Стандартом взаимодействия с реляционной базой данных стал язык SQL. Приемником SQL в 1С является язык запросов. Язык запросов, также как и SQL, является структурированным. Составляющие структуры запроса отвечают на разные вопросы о том, какие данные требуется получить и какие манипуляции с множествами данных необходимо произвести при получении. В простых случаях текст запроса можно написать вручную, однако в сложных случаях, а также при программном формировании, - лучше воспользоваться объектной моделью запроса и использовать объект "Схема запроса". В статье дается описание объектной модели и особенностей работы с ней, а также приводится решение, упрощающее взаимодействие с объектом "Схема запроса".

1 стартмани

24.04.2018    29149    75    kalyaka    34       

Асинхронная запись и чтение файла без использования модальных методов и временных файлов 133

Статья Программист Внешняя обработка (ert,epf) v8 1cv8.cf Абонемент ($m) Практика программирования

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

1 стартмани

10.04.2018    19312    17    Alxby    23       

Заполняем по шаблону (по умолчанию) 68

Инструменты и обработки Программист Архив с данными v8 v8::УФ 1cv8.cf Абонемент ($m) Практика программирования

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

1 стартмани

08.02.2018    18219    20    mvxyz    17       

Бесплатная проверка контрагентов в ФНС (общий модуль с алгоритмом). На примере выводим статус в список справочника контрагентов 124

Статья Программист Конфигурация (md, cf) v8 1cv8.cf Абонемент ($m) Практика программирования

Если вам интересно проверить контрагенте в ФНС, вам поможет данная публикация. Весь алгоритм работы строится на основе данных, полученных с сервиса http://npchk.nalog.ru совершенно бесплатно.

1 стартмани

01.02.2018    25703    62    rpgshnik    46       

Расширение возможностей печати: Вывод произвольного нижнего и верхнего колонтитула 8

Отчеты и формы Программист Внешняя обработка (ert,epf) v8 1cv8.cf Абонемент ($m) Печатные формы документов Практика программирования Универсальные функции

Расширяем функционал вывода нижнего / верхнего колонтитула. Стандартно 1С имеет достаточно ограничений по выводу и наполнению колонтитулов содержимым, взять хотя бы такие, как вывод только текста и отсутствие ограничения на номер конечной страницы. А при разработке кода сталкиваешься с тем, что свой блок с нижним колонтитулом нужно прижимать к низу страницы. Казалось бы быстро решаемый вопрос, но и в нем есть нюансы. Сейчас я расскажу о том, как решалась эта задача. UPD 15.02.2018. Добавлен вывод верхнего колонтитула; Вывод колонтитулов на первой и последней странице управляется параметрами; Научился считать страницы: Добавлено заполнение переменных аналогичных стандартным из колонтитулов; Задаются форматы даты и времени. Ограничения прежние: 1. Повторно сформировать табличный документ после смены параметров страницы интерактивно.; 2. Передавать данные для более плотной печати как можно более мелко нарезанными кусками.

1 стартмани

29.12.2017    23496    21    agent00mouse    0       

Практика доступа в базу 1С через протокол oData. Чтение данных 285

Статья Системный администратор Программист Бизнес-аналитик Внешняя обработка (ert,epf) v8 1cv8.cf Абонемент ($m) Сервисные утилиты Практика программирования Администрирование данных 1С

Для чего нужен доступ в базу 1С через REST-интерфейс по протокол oData? Как его организовать? Как не будучи гуру в JavaScript и .NET получить быстрый визуальный доступ к данным базы 1С? Попробую дать ответ на эти вопросы и прокомментирую некоторые нюансы, с которыми я столкнулся.

1 стартмани

11.12.2017    59836    252    Dementor    44       

Печатная форма, сделанная как расширение конфигурации для БП 3.0. Новые возможности БСП 26

Инструменты и обработки Программист Расширение (cfe) v8 БП3.0 Абонемент ($m) Практика программирования Универсальные печатные формы

Печатные формы на внешних обработках скоро канут в лету. На смену им приходят ПФ, реализованные в виде расширений конфигурации. Не нашел на сайте примеров таких расширений. Привожу пример подобного расширения для БП 3.0.

1 стартмани

06.12.2017    18875    52    kwazi    6       

Простой бесплатный DashBoard с помощью http сервиса 257

Статья Программист Конфигурация (md, cf) v8 Абонемент ($m) Практика программирования

Как создать свой DashBoard без дополнительных затрат и сложных технических доработок.

1 стартмани

25.11.2017    44794    59    dewersia    32       

Полезный код для программистов 1С (часть 1). Управление свойствами элементов формы. Хранение копии данных реквизитов 141

Статья Программист Архив с данными v8 Абонемент ($m) Инструментарий разработчика Практика программирования

У каждого программиста за время работы накапливается полезный инструментарий, которым он привык пользоваться. Естественно и у меня он тоже имеется. И вот решено было немного поделиться с сообществом. Возможно идеи не новые. Более того, допускаю, что реализованы они не самым оптимальным образом. Но ведь для этого сообщество и существует, чтобы делиться с ним, получая обратную связь.

1 стартмани

24.09.2017    32606    17    vandalsvq    80       

Telegram-боты 149

Инструменты и обработки Программист Архив с данными v8 Абонемент ($m) Практика программирования

Описание теории, разбор архитектуры и пример реализации telegram-ботов. Сразу скажу, со структурированием изложения мало что могу поделать. :) редакция от 18.07.2018 Правки последней редакции выделены жирным.

1 стартмани

01.09.2017    22866    119    PLAstic    45       

Макеты СКД 286

Статья Программист Внешний отчет (ert,erf) v8 v8::СКД 1cv8.cf Абонемент ($m) Практика программирования

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

1 стартмани

25.07.2017    71611    109    json    25       

Расширения конфигураций 1С: учимся перехватывать методы 112

Инструменты и обработки Программист Расширение (cfe) v8 v8::УФ 1cv8.cf Абонемент ($m) Практика программирования

В этой статье я на примерах разберу некоторые механизмы расширений конфигураций 1С. А именно «перехваты» методов модуля объекта и «перехваты» событий формы и элементов формы. Данная статья написана с учебными целями, чтобы показать, как при помощи расширений конфигурации можно делать такие доработки, ради которых раньше приходилось снимать конфигурацию с поддержки.

1 стартмани

30.05.2017    86229    14    signum2009    45       

Многопоточность. Универсальный «Менеджер потоков» (фреймворк) с отслеживанием зависимости объектов 177

Статья Программист Архив с данными v8 1cv8.cf Россия Абонемент ($m) Практика программирования Математика и алгоритмы Универсальные функции Производительность и оптимизация (HighLoad)

Восстановление партий, расчет зарплаты, пакетное формирование документов или отчетов - теперь все это стало доступнее. * Есть желание повысить скорость работы медленных алгоритмов! Но... * Нет времени думать о реализации многопоточности? * о запуске и остановке потоков? * о поддержании потоков в рабочем состоянии? * о передаче данных в потоки и как получить ответ из потока? * об организации последовательности? Тогда ЭТО - то что надо!!!

26.05.2017    39795    168    DarkAn    86       

Регулярные выражения – это просто. Построитель и отладчик регулярных выражений 181

Инструменты и обработки Программист Архив с данными v8 1cv8.cf Абонемент ($m) Инструментарий разработчика Практика программирования

Предлагается к использованию построитель регулярных выражений. Выполненный в виде внешней обработки, он позволит строить сложно-структурированные выражения на основе параметрического описания, тестировать их, и в результате получить программный код 1С.

1 стартмани

13.03.2017    23341    112    romasna    47       

Несколько шаблонов для доработки типовых конфигураций 174

Инструменты и обработки Программист Конфигурация (md, cf) v8 v8::УФ Абонемент ($m) Практика программирования Инструментарий разработчика

Предлагаю несколько каркасов для создания новых объектов в типовых конфигурациях. Это выжимка из кода нескольких конфигураций, которая позволит быстро и красиво создавать и дорабатывать объекты метаданных с соблюдением идеологии исходной системы

1 стартмани

03.10.2016    28727    102    json    25       

Простой способ индексирования интервалов 182

Статья Программист Конфигурация (md, cf) v8 Абонемент ($m) Практика программирования

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

1 стартмани

28.09.2016    32610    39    ildarovich    22       

1С: Предприятие + корпоративный чат, как наладить оперативные уведомления за 10 минут 61

Инструменты и обработки Системный администратор Программист Компонента, плагин (dll, vbs,..) v8 Windows Абонемент ($m) Практика программирования

Как сделать автоматические уведомления о разных событиях из 1С в корпоративный чат MyChat для сотрудников компании

1 стартмани

14.08.2016    39187    35    Demanoidos    60       

Хранение файлов в томах на диске (для УПП 1.3) 78

Инструменты и обработки Программист Архив с данными v8 УПП1 Windows Абонемент ($m) Практика программирования

Доработка типовой УПП 1.3 в плане хранения присоединенных файлов вне базы данных

2 стартмани

05.06.2016    44973    6    wowik    27       

БСП 2.3 и БСП 3.0: Просто про выполнение внешней обработки в фоне (c индикацией прогресса выполнения) 187

Инструменты и обработки Программист Внешняя обработка (ert,epf) v8 1cv8.cf Windows Абонемент ($m) Инструментарий разработчика Практика программирования БСП (Библиотека стандартных подсистем)

Простое пояснение о том, как сделать внешнюю обработку с фоновым выполнением и индикацией процесса для любой конфигурации на основе БСП 2.3.2. UPDATE 20/09/19: добавлен вариант обработки с индикацией процента выполнения и статусом выполнения для БСП 3.0.

1 стартмани

18.05.2016    47577    140    rozer    52       

Остатки на каждый день в запросе 34

Инструменты и обработки Программист Внешняя обработка (ert,epf) v8 1cv8.cf УУ Windows Учет ТМЦ Абонемент ($m) Практика программирования

Запрос формирует остатки товаров на каждый день в пределах выбранного периода.

1 стартмани

26.04.2016    36380    19    arakelyan    17       

Выполнение JavaScript кода из 1С в объекте Поле HTML Документа (HTML 5) и вызов события в 1С ПриНажатии 152

Инструменты и обработки Программист Внешняя обработка (ert,epf) v8 1cv8.cf Россия Windows Абонемент ($m) Практика программирования

Пример выполнения JS кода из 1С в Поле HTML Документа под управляемыми формами, с удобным получением результата в 1С(С помощью вызова привязанного события ПриНажатии к элементу ПолеHTMLДокумента)

1 стартмани

22.03.2016    62540    137    igo1    50       

Количество дней недели (понедельников/вторников/...) в заданном диапазоне одним запросом 29

Инструменты и обработки Программист Внешняя обработка (ert,epf) v8 Абонемент ($m) Практика программирования

При реализации периодического авто-заполнения маршрутных листов по графику (недельному) необходимо было просчитать стоимость всего периода, с условием выездов только по определенным дням. Заморачиваться с обходом результата не хотелось. Пришлось написать "Небольшой" запрос.

1 стартмани

03.03.2016    12818    1    Alexander.Shvets    5       

Простые радости жизни программиста 1С: выбор типа значения 51

Инструменты и обработки Программист Внешняя обработка (ert,epf) v8 1cv8.cf Абонемент ($m) Практика программирования Работа с интерфейсом

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

1 стартмани

17.02.2016    39897    45    yuraos    17       

Отображение прогресса выполнения длительных операций в БСП и их отладка в текущем сеансе. 162

Инструменты и обработки Программист Внешняя обработка (ert,epf) v8 1cv8.cf Windows Абонемент ($m) Практика программирования БСП (Библиотека стандартных подсистем)

В статье описан способ исполнения длительных операций в конфигурациях, в которых используется библиотека стандартных подсистем, с визуализацией прогресса исполнения и отображения хода обработки данных. Также дается краткое описание процесса отладки длительных операций в текущем сеансе.

1 стартмани

17.02.2016    41880    146    balanton    20       

Яндекс.Деньги "Благотворительность" 17

Инструменты и обработки Программист Внешняя обработка (ert,epf) v8 1cv8.cf Windows Абонемент ($m) Инструментарий разработчика Практика программирования

Яндекс.Деньги теперь в 1С. Форма для приема благотворительных взносов. Форму легко сделать и вставить на любую страницу сайта или блога. Платежи будут приходить на ваш кошелек. На форме есть три способа платежа: из кошелька, с банковской карты, с баланса мобильного.

1 стартмани

16.02.2016    18169    9    Tatitutu    5       

Мастер рассылки e-mail 2.2 для управляемых форм 9

Инструменты и обработки Программист Внешняя обработка (ert,epf) v8 v8::УФ ERP2 БП3.0 УТ11 Абонемент ($m) Практика программирования Email

Для пользователей: переделанный из старый разработки под 8.2 с использованием библиотеки Мастер рассылки e-mail 2.2 (ERP, УТ, БП) (Только управляемые формы), который теперь может запускаться под любой версией платформы с разрешенными или запрещенными модальными/синхронными вызовами в конфигурации. Также удобный выбор e-mail и их владельцев с помощью отбора динамического списка по любым критериям и галочки исключения.

1 стартмани

29.12.2015    31328    20    milkers    4       

Нечеткий поиск одним запросом 37

Инструменты и обработки Программист Внешняя обработка (ert,epf) v8 1cv8.cf Абонемент ($m) Практика программирования

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

1 стартмани

28.12.2015    20099    57    vasvl123    9       

Передача больших пакетов через веб-сервисы 138

Инструменты и обработки Системный администратор Программист Конфигурация (md, cf) v8 Абонемент ($m) Практика программирования Администрирование данных 1С Внешние источники данных

Реализация механизма передачи больших пакетов через веб-сервисы. С его помощью передать файл размером в несколько гигабайт не составит проблем.

1 стартмани

06.12.2015    43390    44    YPermitin    19       

Пример связи 1С и мессенджера Telegram. Получение данных из 1С запросом из Telegram 245

Инструменты и обработки Системный администратор Программист Внешняя обработка (ert,epf) v8 1cv8.cf Абонемент ($m) Практика программирования Внешние источники данных

В результате чтения публикации Вы получите готовую внешнюю обработку, позволяющую получать из 1С данные, запрашиваемые через Telegram. В данной статье рассмотрим следующее: Использование HTTPСоединение; Чтение JSON для версии 1С 8.3.6 и выше, а также аналог JSON для версии 1С ниже 8.3.6; Подключение обработчика ожидания; Некоторые основные возможности API Telegram; Как создать бота для Telegram; Программное создание колонок дерева на управляемой форме;

1 стартмани

19.11.2015    72099    424    Luchik    199