0 / 1 / 2
Регистрация: 30.10.2012
Сообщений: 113
1

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

19.11.2013, 01:26. Показов 1272. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.11.2013, 01:26
Ответы с готовыми решениями:

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

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

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

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

1
351 / 344 / 279
Регистрация: 21.05.2013
Сообщений: 1,312
19.11.2013, 11:34 2
почитай поиск в ширину (дискретная матиматика - граф)там небольшая процедурка которая тебе поможет
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.11.2013, 11:34
Помогаю со студенческими работами здесь

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru