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

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

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

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

C++ Найти минимальные в векторе
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     минимальные расстояния на графе
Ответ Создать тему
Опции темы

Текущее время: 20:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru