Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 17.02.2010, 09:07   #1
Vohakisa
Пользователь
 
Регистрация: 11.05.2009
Сообщений: 47
По умолчанию Задание "Кратчайший путь"

Дали вот такое задание, написать программу, которая будет находить кратчайший путь между двумя заданными точками, насколько я понял это что-то с теории графов. Хотелось бы услышать, от знающих людей, какие алгоритмы лучше использовать (если можно, с ссылками на описание алгоритмов).
Vohakisa вне форума Ответить с цитированием
Старый 17.02.2010, 09:13   #2
Google2010
Форумчанин
 
Регистрация: 16.02.2010
Сообщений: 316
По умолчанию

алгоритмы о путях
Google2010 вне форума Ответить с цитированием
Старый 17.02.2010, 12:59   #4
Vohakisa
Пользователь
 
Регистрация: 11.05.2009
Сообщений: 47
По умолчанию

Спасибо за ссылки, очень помогли, решил использовать алгоритм дейкстра.

Хотелось бы так же, чтобы программа выводила полный путь ко всем вершинам или хотя бы к одной конкретной, думаю для этого надо добавить отдельный массив. Буду рад, если кто то ответит по этому поводу.

Код программы:
Код:
n:=10;//Количество вершин
fillchar(S,sizeof(S),0);
fillchar(C,sizeof(C),10000);
q:=StrToInt(E_1.Text);//Расстояние до начальной вершины
if (q<1) or (q>10) then q:=1;
C[q]:=0;
for i:=1 to n do  begin
  m:=1000;
  for j:=1 to n do
  if( (C[j]<=m) and (S[j]=0) ) then
  begin
    m:=C[q];
    v:=j;
  end;
  S[v]:=1;
  SG_S.Cells[i,0]:=IntToStr(S[i]);
  for j:=1 to n do
    if ( (a[v,j]<> -1) and (S[j]=0) and (C[v]+a[v,j]<C[j])) then
      C[j]:=C[v]+a[v,j];
end;
LB_1.Clear;
for i:=1 to n do
LB_1.Items.Append(IntToStr(q)
  +' to '+IntToStr(i)+': '+IntToStr(C[i]));
Вот вся программа
alg_deuxtra.rar

P.S. Набросал на скорую руку, поэтому оформления в ней никакого.

up

Всё ещё думаю то тут надо добавить массив, но не могу представить всё это.

P.S. Надеюсь раз в день можно темку апать. В правилах ничего про UP темы не видел.

Последний раз редактировалось Stilet; 18.02.2010 в 13:35.
Vohakisa вне форума Ответить с цитированием
Старый 18.02.2010, 12:08   #5
Sasha_Smirnov
Особый статус
Участник клуба
 
Аватар для Sasha_Smirnov
 
Регистрация: 24.11.2008
Сообщений: 1,535
По умолчанию

Непонятно, почему "1 to 5" даёт путь 12. Желательно срабатывание и по клавише Enter. Ну и графическая иллюстрация.
P/s: смысл «апать»? Это только раздует форум.
Sasha_Smirnov вне форума Ответить с цитированием
Старый 18.02.2010, 12:39   #6
Vohakisa
Пользователь
 
Регистрация: 11.05.2009
Сообщений: 47
По умолчанию

Программа заполняет матрицу смежности рандомно, пару раз проверил, считает вроде как правильно, выше я отписался что оформление меня на данный момент не интересует, главное чтобы работала.
Vohakisa вне форума Ответить с цитированием
Старый 18.02.2010, 12:45   #7
Sasha_Smirnov
Особый статус
Участник клуба
 
Аватар для Sasha_Smirnov
 
Регистрация: 24.11.2008
Сообщений: 1,535
По умолчанию

Ну прямым текстом стоял путь "–1" от 1 к 5 (и от 5 к 1). Откуда 12, путь не прямой, что ли? Я ж говорю: без картинки судить трудно.
Sasha_Smirnov вне форума Ответить с цитированием
Старый 18.02.2010, 12:59   #8
Vohakisa
Пользователь
 
Регистрация: 11.05.2009
Сообщений: 47
По умолчанию

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


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
"ОКРВВЕРХ", "ОКР", "ЕСЛИ". Как бы их связать. Каравай Microsoft Office Excel 13 17.02.2010 09:53
при вводе на листе "магазин"- код товара появлялось "описание" товара из "склада" с "продажной ценой" aleksei78 Microsoft Office Excel 13 25.08.2009 12:04
Как добавить програмно "Назначенные задания" новое задание??? Paul Hindenburg Общие вопросы Delphi 3 05.08.2009 17:07