Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/7: Рейтинг темы: голосов - 7, средняя оценка - 5.00
0 / 1 / 2
Регистрация: 30.10.2012
Сообщений: 113

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

19.11.2013, 01:26. Показов 1517. Ответов 1
Метки нет (Все метки)

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

Что смог сделать:
Pascal
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
Program LR9_Graf;
uses crt;
const MaxN=5;
INF = 1000000000; {бесконечность}
type Matrix = array[1..MaxN,1..MaxN] of longint; {тип матрицы смежности. M[i,j] = true, если существует ребро, идущее от вершины i к j }
 
var Dor:Matrix; Sv:integer; {вершина}
    D:array[1..MaxN] of integer;
 
Procedure Input_Table(var A:Matrix; N:longint);
var i,j:longint;
begin
   Randomize;
   For i:=1 to N do begin
    For j:=1 to N do begin
     A[i,j]:=random(100);
     if (A[i,j]=0) and (i<>j) then A[i,j]:=inf;
    end;
   end;
end;
 
Procedure Output_Table(var A:Matrix; N:longint);
var i,j:longint;
begin
    For i:=1 to N do begin
     For j:=1 to N do begin
      write(A[i,j]:4);
     end;
     writeln;
    end;
end;
 
 
 
procedure SearchDeikstr(var A:Matrix; N,s:integer); {процедура ввода матрицы смежности A(N, N) }
var i,j,v,min:longint; Visit:array[1..5] of boolean; {массив посещенности}
begin
    Visit[s]:=true; {вершина S посещена}
    For i:=1 to N do D[i]:=A[s,i]; {изначальный массив расстояний}
     For i:=1 to N-1 do begin {на каждом шаге находим минимальное решение и пытаемся его улучшить}
      min:=inf;
      For j:=1 to N do
       if ((not Visit[j]) and (D[j]<min)) then begin
        min:=A[i, j]; {минимальное расстояние}
        v:=j; {найденная вершина}
      end;
     end;
    For j:=1 to N do
     if (D[j]>D[v]+A[v, j]) and (D[v]<inf) and (A[v, j]<inf) then D[j]:=D[v]+A[v, j]; {пытаемся улучшить решение.  Если расстояние больше чем сума расстояния до текущей вершины и линии ребра, то уменьшаем его}
    s := v; {новая текущая вершина}
    Visit[v]:=true; {и она отмечается посещенной}
    writeln('Минимальное расстояние= ',min);
end;
 
BEGIN
    clrscr;
    Input_Table(Dor, MaxN);
    Output_Table(Dor, MaxN);
    SearchDeikstr(Dor, MaxN, Sv);
    readkey
END.
Подправьте плиз процедуру по нахождению длины кратчайшего маршрута, указаний последовательности торговых точек, при этом маршрут должен проходить одну и туже точку не более одного раза.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
19.11.2013, 01:26
Ответы с готовыми решениями:

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

Найти кратчайший маршрут, начинающийся в 1-м городе и проходящий через все остальные города
Имеется n городов. Некоторые из них соединены дорогами известной длины. Вся система дорог задана квадратной матрицей порядка n, элемент аij...

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

1
 Аватар для newyork7776
351 / 344 / 279
Регистрация: 21.05.2013
Сообщений: 1,312
19.11.2013, 11:34
почитай поиск в ширину (дискретная матиматика - граф)там небольшая процедурка которая тебе поможет
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
19.11.2013, 11:34
Помогаю со студенческими работами здесь

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

Кратчайший маршрут робота
Нужно написать программу для определения маршрута робота.В клеточном поле двигается робот. Имеется система координат x и y (номер клетки по...

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

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

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Новые блоги и статьи
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly
8Observer8 24.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы
anaschu 24.01.2026
Решили писать научную статью с неким РОманом
http://iceja.net/ математические сервисы
iceja 20.01.2026
Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru