Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
ObliviusM
1 / 1 / 0
Регистрация: 04.12.2010
Сообщений: 5
#1

минимальные расстояния на графе - C++

21.05.2011, 17:58. Просмотров 1221. Ответов 6
Метки нет (Все метки)

Здравствуйте, уважаемые программисты. Задача такова:

Задано N домов и M дорог. Дома пронумерованы от 1 до N. Каждая дорога определяется тройкой чисел (i,j,k), где i - номер дома вначале дороги, j - номер дома в конце дороги, k - длинна дороги. В каждом доме живёт по одному человеку. Найти точку, что есть местом встречи всех людей, от которой суммарное расстояние ко всем домам будет минимальным. Если точка лежит на дороге, то определить номер дома в начале и в конце этой дороги и расстояние от первого из этих домов. Если точка совпадает с домом, то определить номер этого дома.

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

Прошу подкинуть какие-то идеи решения.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.05.2011, 17:58     минимальные расстояния на графе
Посмотрите здесь:

Измерение расстояния. C++ - C++
такая задача: Написать программу для вычисления расстояния между колонками и микрофоном(на с++). Т.е. говоришь в микрофон и нам выводит...

Определение большего расстояния - C++
Помогите пожалуйста решить задачу: На плоскости заданы своими координатами n точек. Составить программу, определяющую, между какими из...

Найти расстояния от точки до прямых - C++
Описать процедуру Dist(Px,Py,Ax,Ay,Bx,By,D), находящую расстояние*D от точки*P до прямой*AB по формуле*D*=*2SPAB*/*|AB|, где*SPAB —...

Упорядочение записей по убыванию расстояния - C++
упорядочение записей по убыванию расстояния в километрах; Вот код к задаче:const int n=3; const int N=3; #include <stdio.h> ...

Найти расстояния между точками - C++
Пожалуйста помогите с задачей.На плоскости есть три точки с координатами A(2;3)B(-1;4)C(0;0).Найти расстояния между точками AB BC CA и...

Нахождение расстояния между точками - C++
Вводится количество точек, потом их координаты. Программа должна вывести общее расстояние между ними. Помогите с решением.

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryLaptev
Эксперт С++
1039 / 818 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
21.05.2011, 18:08     минимальные расстояния на графе #2
Граф представляется матрицей расстояний. Тогда Алгоритм флойда-уоршала в аддитивном виде...
Можно алгоритм Дейкстры, но там одно расстояние находится - от одной заданной вершины до другой.
ObliviusM
1 / 1 / 0
Регистрация: 04.12.2010
Сообщений: 5
21.05.2011, 18:29  [ТС]     минимальные расстояния на графе #3
Но так мы найдём расстояния только для вершин. И можна будет определить вершину с минимальными расстояниями к остальным вершинам . Но в задаче нужно найти именно точку на ребре, от которой расстояния к вершинам будут минимальны.
ValeryLaptev
Эксперт С++
1039 / 818 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
21.05.2011, 18:47     минимальные расстояния на графе #4
Два варианта. Либо это задача Штайнера. Либо минимальный остов.
ObliviusM
1 / 1 / 0
Регистрация: 04.12.2010
Сообщений: 5
21.05.2011, 19:04  [ТС]     минимальные расстояния на графе #5
С задачей Штейнера как-то трудновато разобраться) А вот минимальное остовное дерево кажется вполне подходит. Большое спасибо, буду решать
ValeryLaptev
Эксперт С++
1039 / 818 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
21.05.2011, 19:07     минимальные расстояния на графе #6
Тогда самый простой вариант - алгоритм Краскала. Или алгоритм Прима.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.05.2011, 19:36     минимальные расстояния на графе
Еще ссылки по теме:

Минимальные значения - C++
Всем привет. У меня девушка учится на 3 курсе в институте. Ей дали задачу, которую она не может решить, а я в этом деле не разбираюсь....

формула пересчета расстояния из километров в версты - C++
запишите в виде конструкции присваивания формулу пересчета расстояния из километров в версты( одна верста это 1066,8 м )

Нахождение кратчайшего расстояния методом Флойда - C++
Программа спрашивает кол-во вершин . И должно последовательно вводится расстояние между всеми вершинами. НО вводится лишь расстояние...

Зависимость преодолённого бегуном расстояния от времени - C++
Нужна подсказка в решении задачи, новичку! (толчок в нужном направлении) Всем привет! есть такая задача, по которой надо написать...


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

Или воспользуйтесь поиском по форуму:
ObliviusM
1 / 1 / 0
Регистрация: 04.12.2010
Сообщений: 5
21.05.2011, 19:36  [ТС]     минимальные расстояния на графе #7
Да. Я думаю так:
1 найти минимальный остов через Прима;
2 построить для остова матрицу минимальных расстояний через Флойда-Уоршала;
3 Выбрать две вершины, у которых сумма расстояний к вершинам будет наименьшей(по идеи, они будут соеденены ребром и это ребро будет содержать искомую точку);
4 а дальше по пропорции найти на ребре "средину" для расстояний.
как-то так
Yandex
Объявления
21.05.2011, 19:36     минимальные расстояния на графе
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru