Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > С/С++
Перезагрузить страницу Задача на графы как их правильно решать
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
7ema 7ema вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 19.10.2005
По умолчанию Задача на графы как их правильно решать - 19.10.2005, 10:27

вот задание:

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

Код:
#include<stdio.h>
#define P 20
#include<conio.h>
 int findmin(int V,int U)
     {




     return;
     }
 int n,m[P][P],min;

int  main()
 {
 int i,k,r,OTVET,Min[P][P]={0},MinVektor[P]={0};

 scanf("%d",&n);

 for(k=0;k<n;k++)
   for(i=0;i<n;i++)
    {
    scanf("%d",&r);
    m[k][i]=r;
    min=min+m[k][i];
    }


  for(k=0; k<n;k++)
   for(i=0; i<n; i++)   if(i!=k && m[k][i]==0) Min[k][i]=findmin(k,i);


   for(k=0; k<n;k++)
       for(i=0; i<n; i++)
    if(i!=k )if (m[k][i]!=0) MinVektor[k]=MinVektor[k]+m[k][i];
      else MinVektor[k]=MinVektor[k]+Min[k][i];



     for(i=0;i<n;i++)  {
     printf("%d. %dn",i,MinVektor[i]);
    if(MinVektor[i]<min) { min=MinVektor[i]; OTVET=i; }
         }
    printf("Eto gorod -=%d=-",OTVET);


 getch();
 return 0;
 }
Ответить с цитированием
  (#2 (permalink)) Старый
_TNT_ _TNT_ вне форума
Member
 
Сообщений: 448
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 04.02.2005
По умолчанию 19.10.2005, 19:19

что конкретно тебе нужно? твою прогу "исследовать" никому не хочется, а вопрос так и не понятен? нужны алгоритмы поиска оптимального пути?
Ответить с цитированием
  (#3 (permalink)) Старый
djonkiller djonkiller вне форума
Member
 
Сообщений: 64
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 30.05.2005
По умолчанию 19.10.2005, 21:25

посмотри тут:
http://algolist.manual.ru/games/wavealg.php
http://www.codenet.ru/progr/alg/way.php
http://doc.mpv.ru/steps/theory/volna.html
на паскале прога работает на си не проверял. могу еще на delphi предложить:

http://www.hardforum.ru/t61612
Ответить с цитированием
  (#4 (permalink)) Старый
7ema 7ema вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 19.10.2005
По умолчанию 19.10.2005, 23:05

Цитата:
Originally posted by _TNT_
[b]что конкретно тебе нужно? твою прогу "исследовать" никому не хочется, а вопрос так и не понятен? нужны алгоритмы поиска оптимального пути?
нужно написать функцию findmin(int V,int U) , которая будет искать кратчайший путь между двумя городами. Подошел бы алгоритм Дейкстра ( http://vmk.hut.ru/cgi-bin/index.cgi?go=lec...s&show=deikstra ), но он ищет кратчайшие пути от заданного города до всех остальных, для моего вар-та программы это не подходит.
Ответить с цитированием
  (#5 (permalink)) Старый
krutoj_pablo krutoj_pablo вне форума
Member
 
Сообщений: 150
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 13.01.2005
По умолчанию 20.10.2005, 15:28

Цитата:
нужно написать функцию findmin(int V,int U) , которая будет искать кратчайший путь между двумя городами. Подошел бы алгоритм Дейкстра ( http://vmk.hut.ru/cgi-bin/index.cgi?go=lec...s&show=deikstra ), но он ищет кратчайшие пути от заданного города до всех остальных, для моего вар-та программы это не подходит.
Как раз таки здесь Алгоримт Дейкстры очень даже подходит, он создаёт дерево крадчайших путей, ну а если есть дерево путей, то найти какойто один из него остаётся пустяковой задачей.

Еффективную реализацию можно найти в библиотеке boost, на www.boost.org
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
7ema 7ema вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 19.10.2005
По умолчанию 20.10.2005, 16:19

Цитата:
Originally posted by krutoj_pablo
[b]<div class='quotetop'>Цитата
Цитата:
нужно написать функцию findmin(int V,int U) , которая будет искать кратчайший путь между двумя городами. Подошел бы алгоритм Дейкстра ( http://vmk.hut.ru/cgi-bin/index.cgi?go=lec...s&show=deikstra ), но он ищет кратчайшие пути от заданного города до всех остальных, для моего вар-та программы это не подходит.
Как раз таки здесь Алгоримт Дейкстры очень даже подходит, он создаёт дерево крадчайших путей, ну а если есть дерево путей, то найти какойто один из него остаётся пустяковой задачей.

Еффективную реализацию можно найти в библиотеке boost, на www.boost.org[/quote]

Да, я наверно так и сделаю, просто не хотел считать ненужные ветки дерева, т.к. они и так известны (заданы в матрице.)
Ответить с цитированием
  (#7 (permalink)) Старый
Васисуалий Васисуалий вне форума
Новичок
 
Сообщений: 3
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 13.11.2010
По умолчанию 13.11.2010, 14:11

это задача поиска медианы, видел реализацию на сайте Задачи оптимизации
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Правильно ли составлена задача? Gores Visual C++ 1 06.03.2012 17:11
не знаю как решать Tolian92 Pascal 2 12.12.2011 00:30
Транспортная задача как ее решать Perepel Delphi 0 05.06.2011 23:02
Задача на графы, помогите ускорить salamandra91 Prolog 0 07.01.2011 23:48
Задача на графы german25rus Prolog 1 24.12.2010 16:58
Задача на указатели: правильно ли я понял условие? Gock C++ Builder 5 07.09.2010 09:12
решена задача в паскале правильно или нет? durachok Форум программистов 4 27.12.2008 19:00
Excel как решать задачи shalun Visual Basic 5 27.10.2008 18:27
Как решать задачи на последовательность iit3 Pascal 1 04.09.2005 04:29
Как решать задачи на С++ paspartu Вопросы начинающих программистов 1 04.05.2005 17:31
Помогаю решать вопросы с VB Dominator Visual Basic 9 23.01.2005 23:22
Как решать задачи с алгоритмом NP Anonymous Алгоритмы 1 22.03.2003 22:07



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов