Реклама на этом месте
Форум 1С
Форум 1С
Программистам. Бухгалтерам. Администраторам. Пользователям
Задай вопрос - получи решение проблемы. Без троллинга и флуда.
21 Янв 2018, 17:40
МультиВход
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Не получили письмо с кодом активации?
 
collapse

Автор Тема: Алгоритм нахождения кратчайшего пути  (Прочитано 1045 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Юлия56

  • *
  • Сообщений: 7
  • РЕПУТАЦИЯ: 0
  • Регистрация: 2014-11-04
  • Сайт: 
В программе реализуется алгоритм нахождения кратчайшего пути по алгоритму Дейкстры. Есть код, но необходимо составить блок схему реализации алгоритма, а я не могу собрать все в кучу. Помогите пожалуйста!

Функция ПоискПути(ПунктОтпр, ПунктНазнач, Путь)
Функция ПоискПути(ПунктОтпр, ПунктНазнач, Путь)//используется, по регистру Тарифы
// Функция возвращает стоимость доставки 1 тонны груза
//В переменную Путь - записываются пункты следования
Перем i,j,k,//счетчики циклов
A,B,//путь из точки A в B
m;//размер графа
Запрос=Новый Запрос;
ТекстЗапроса=
"ВЫБРАТЬ
| Тарифы.ПунктОтправления КАК Пункты
|ПОМЕСТИТЬ времТЗ
|ИЗ
| РегистрСведений.Тарифы КАК Тарифы
|
|ОБЪЕДИНИТЬ ВСЕ
|
|ВЫБРАТЬ
| Тарифы.ПунктНазначения
|ИЗ
| РегистрСведений.Тарифы КАК Тарифы
|;
|
|////////////////////////////////////////////////////////////////////////////////
|ВЫБРАТЬ
| времТЗ.Пункты КАК Пункты
|ИЗ
| времТЗ КАК времТЗ
|
|СГРУППИРОВАТЬ ПО
| времТЗ.Пункты";
Запрос.Текст=ТекстЗапроса;
Результат=Запрос.Выполнить();
Выборка=Результат.Выбрать();
m=Выборка.Количество();
СписокПунктов=Новый СписокЗначений;
ТЗ=Результат.Выгрузить();
СписокПунктов.ЗагрузитьЗначения(ТЗ.ВыгрузитьКолонку("Пункты"));
//Для п=0 По СписокПунктов.Количество()-1 Цикл
// Сообщить(СписокПунктов[п]);
//КонецЦикла;

строкМасс = Новый Массив(m,m);
ИсхМасс = Новый Массив(m,m);
Для i=0 По m-1 Цикл
Для j=0 По m-1 Цикл
СтрокМасс[i][j]="";
ИсхМасс[i][j]=0;
КонецЦикла;
КонецЦикла;

ТекстЗапроса=
"ВЫБРАТЬ
| Тарифы.ПунктОтправления КАК ПунктОтправления,
| Тарифы.ПунктНазначения КАК ПунктНазначения,
| СУММА(Тарифы.СтоимостьАвто) КАК СтоимостьАвто,
| СУММА(Тарифы.СтоимостьАвиа) КАК СтоимостьАвиа,
| СУММА(Тарифы.СтоимостьЖД) КАК СтоимостьЖД,
| Тарифы.ПунктОтправления.Наименование КАК ПунктОтправленияНаименование,
| Тарифы.ПунктНазначения.Наименование КАК ПунктНазначенияНаименование
|ИЗ
| РегистрСведений.Тарифы КАК Тарифы
|
|СГРУППИРОВАТЬ ПО
| Тарифы.ПунктОтправления,
| Тарифы.ПунктНазначения,
| Тарифы.ПунктОтправления.Наименование,
| Тарифы.ПунктНазначения.Наименование
|ИТОГИ ПО
| ПунктОтправления,
| ПунктНазначения";
Запрос.Текст=ТекстЗапроса;
Результат=Запрос.Выполнить();
//ТабличноеПоле2=Результат.Выгрузить();
//ЭлементыФормы.ТабличноеПоле2.СоздатьКолонки();
ВыборкаОтправления=Результат.Выбрать(ОбходРезультатаЗапроса.ПоГруппировкам);
i=0; j=0; Зап_i=""; Зап_j="";

Пока ВыборкаОтправления.Следующий() Цикл
ВыборкаНазначение=ВыборкаОтправления.Выбрать(ОбходРезультатаЗапроса.ПоГруппировкам);
ПОтпр=ВыборкаОтправления.ПунктОтправления;
i=СписокПунктов.Индекс(СписокПунктов.НайтиПоЗначению(ПОтпр));
Если ПОтпр=ПунктОтпр Тогда
//сообщить("пОтпр="+Потпр+" i="+Строка(i));
Зап_i=i;
КонецЕсли;

Пока ВыборкаНазначение.Следующий() Цикл
ПНазн=ВыборкаНазначение.ПунктНазначения;
j=СписокПунктов.Индекс(СписокПунктов.НайтиПоЗначению(ПНазн));
Если ПНазн=ПунктНазнач Тогда
//сообщить("пНазн="+ПНазн+" j="+Строка(j));
Зап_j=j;
КонецЕсли;
Если ЭлементыФормы.СпособДоставки.Значение=Перечисления.СпособыДоставки.Авто Тогда
Стоим=ВыборкаНазначение.СтоимостьАВто;
ИначеЕсли ЭлементыФормы.СпособДоставки.Значение=Перечисления.СпособыДоставки.Авиа Тогда
Стоим=ВыборкаНазначение.СтоимостьАвиа;
ИначеЕсли ЭлементыФормы.СпособДоставки.Значение=Перечисления.СпособыДоставки.ЖелДор Тогда
Стоим=ВыборкаНазначение.СтоимостьЖД;
КонецЕсли;
//Сообщить("Отпр="+ПОтпр+" Назн="+ПунктНазнач+" Стом="+Стоим+" Стом="+ТипЗнч(Стоим));
ИсхМасс[i][j]=Стоим;//Заполение массива расстояний!
//j=j+1;
КонецЦикла;
//i=i+1;
//j=0;
КонецЦикла;
Если (Зап_i="")ИЛИ(Зап_j="") Тогда
Сообщить("Для выбранных городов не указаны тарифы на перевозку, рассчет оптимального пути не возможен!");
возврат 0;
КонецЕсли;
//--------------------------------------------------
//Для i=0 По m-1 Цикл
// Для j=0 По m-1 Цикл
// Линия = Новый Линия(ТипЛинииЯчейкиТабличногоДокумента.Сплошная,2);
// ЭлементыФормы.ПолеТабличногоДокумента1.Область(i+1,j+1).Обвести(Линия,Линия,Линия,Линия);
// ЭлементыФормы.ПолеТабличногоДокумента1.Область(i+1,j+1).ШиринаКолонки=8;
// //ЭлементыФормы.ПолеТабличногоДокумента2.Область(i+1,j+1).Текст=СтрокМасс[i][j];
// ЭлементыФормы.ПолеТабличногоДокумента1.Область(i+1,j+1).Текст=ИсхМасс[i][j];
// КонецЦикла;
//КонецЦикла;
//--------------------------------------------------------------------------------
//Поиск кратчайшего пути
Для k=0 по m-1 Цикл
Для i=0 по m-1 Цикл
//стр="";
Для j=0 по m-1 Цикл

//Если (i<=j) Тогда
Если (ИсхМасс[i][k]<>0)И(ИсхМасс[k][j]<>0)И(i<>j) Тогда
//Сообщить(строка(k)+">"+строка(i)+">"+строка(j)+" = "+строка(ИсхМасс[i][j]));
Если ((ИсхМасс[i][k]+ИсхМасс[k][j])<ИсхМасс[i][j])ИЛИ(ИсхМасс[i][j]=0) Тогда
ИсхМасс[i][j]=ИсхМасс[i][k]+ИсхМасс[k][j];
//Сообщить("Вход: "+строка(k)+">"+строка(i)+">"+строка(j)+" = "+строка(ИсхМасс[i][j]));
текЗнач=СтрокМасс[i][k];
Если текЗнач="" Тогда
СтрокМасс[i][j]=строка(i)+" "+строка(k)+" "+строка(j);
Иначе
СтрокМасс[i][j]=СтрокМасс[i][k]+" "+строка(j);
КонецЕсли;
КонецЕсли;
КонецЕсли;
//КонецЕсли;
КонецЦикла;
КонецЦикла;
КонецЦикла;
//--------------------------------------------------
//Для i=0 По m-1 Цикл
// Для j=0 По m-1 Цикл
// Линия = Новый Линия(ТипЛинииЯчейкиТабличногоДокумента.Сплошная,2);
// ЭлементыФормы.ПолеТабличногоДокумента2.Область(i+1,j+1).Обвести(Линия,Линия,Линия,Линия);
// ЭлементыФормы.ПолеТабличногоДокумента2.Область(i+1,j+1).ШиринаКолонки=8;
// //ЭлементыФормы.ПолеТабличногоДокумента2.Область(i+1,j+1).Текст=СтрокМасс[i][j];
// ЭлементыФормы.ПолеТабличногоДокумента2.Область(i+1,j+1).Текст=ИсхМасс[i][j];
// КонецЦикла;
//КонецЦикла;
//--------------------------------------------------
ПунктыСледования=СокрЛП(СтрокМасс[Зап_i][Зап_j]);
Если СтрДлина(ПунктыСледования)>0 Тогда
Пока СтрДлина(ПунктыСледования)>0 Цикл
Позиция=Найти(ПунктыСледования," ");
Если позиция=0 Тогда
рез1=Лев(ПунктыСледования,1);
ПунктыСледования="";
Иначе
рез1=Лев(ПунктыСледования,Позиция-1);
КонецЕсли;
текПункт=СписокПунктов.Получить(Число(рез1));
Путь=Путь+" -> "+текПункт;
ПунктыСледования=Сред(ПунктыСледования,Позиция+1);
КонецЦикла;
Путь = Сред(Путь,5);
Иначе
Путь = ПунктОтпр.Наименование+" -> "+ПунктНазнач.Наименование;
КонецЕсли;
возврат ИсхМасс[Зап_i][Зап_j];
КонецФункции /


Оффлайн дфтын

  • Могу решить ЛЮБУЮ задачу в 1С и не только.. С вопросами в личку:)
  • *****
  • Сообщений: 2720
  • РЕПУТАЦИЯ: 325
  • КПД: 12%
  • 1С наше все
  • Регистрация: 2014-04-29
    • Skype: Soprov1C
  • Компания: Корпорация зонтиков
  • Профессия: Разработчик 1С
и что вы хотите чтобы мы сделали?
Нарисовали блок схему?

p.s.
Запросы - гениальные:)
Помог? Нажми - Спасибо :)
skype: Soprov1C


Теги:
 

Часть четвертая: переход на «1С» версии «3.0». Где в программе находятся «Параметры учета»? Алгоритм настройки кадрового учета в новой версии программы «1С»

Автор 1cwikiРаздел Зарплата и управление персоналом

Ответов: 0
Просмотров: 4146
Последний ответ 20 Мар 2015, 12:58
от 1cwiki
Табличная часть через "Произвольный алгоритм" в Универс. подб. и обр. объектов

Автор Mixailo333Раздел Конфигурирование, программирование в "1С - Предприятие 8"

Ответов: 9
Просмотров: 9526
Последний ответ 14 Май 2013, 22:48
от Dethmontt
Розница,не могу придумать алгоритм Новичек), треб помощь в понимании логики проц

Автор tradРаздел Конфигурирование, программирование в "1С - Предприятие 8"

Ответов: 60
Просмотров: 17654
Последний ответ 30 Ноя 2010, 08:31
от trad
Переход на программу «ЗУП 3.0»: алгоритм подготовки и настройки переноса информации с «1С ЗУП» редакции «2.5»

Автор 1cwikiРаздел Зарплата и управление персоналом

Ответов: 0
Просмотров: 3895
Последний ответ 10 Мар 2015, 16:37
от 1cwiki
Алгоритм загрузки изображений из excel по ссылке URL в реквизит основное изображение

Автор nikioioioРаздел Конфигурирование, программирование в "1С - Предприятие 8"

Ответов: 0
Просмотров: 1074
Последний ответ 23 Мар 2016, 05:43
от nikioioio

* Живое общение

Не устроил ответ?

Зарегистрируйся и задай свой вопрос. Живое общение приносит результат намного быстрее.


Зарегистрироваться

* Реклама

* Поиск

* Последние задачи на разработку (фриланс)

* Реклама

* Последние вакансии

* Топ 10 авторов за месяц

Геннадий ОбьГЭС Геннадий ОбьГЭС
100 Сообщений
AIFrame
66 Сообщений
alex0402
32 Сообщений
kiksi
26 Сообщений
pavl_vs
24 Сообщений
alexandr_ll
18 Сообщений
andron81_81
16 Сообщений
Norfolk
16 Сообщений
KOI8-R
14 Сообщений
MuI_I_Ika MuI_I_Ika
13 Сообщений

* Кто онлайн

  • Точка Гостей: 384
  • Точка Скрытых: 0
  • Точка Пользователей: 5
  • Точка Сейчас на форуме:

* Облако тэгов

* Форум 1С с мобильного

* Инструменты

* Дополнительно

Поиск

 
SimplePortal 2.3.5 © 2008-2012, SimplePortal