man Беллман-Форд

https://ru.wikipedia.org/wiki/Задача_о_кратчайшем_пути

и дальше по ссылкам, преподают это на первых курсах пту

и дальше по ссылкам, преподают это на первых курсах пту

Потом такие как ты из этого ПТУ и рисуют маршрут по дороге с одностороннем движением в обратную сторону.

Значимость данной задачи определяется ее различными практическими применениями[⇨]. Например в GPS-навигаторах, где осуществляется поиск кратчайшего пути между двумя перекрестками. В качестве вершин выступают перекрестки, а дороги являются ребрами, которые лежат между ними. Сумма расстояний всех дорог между перекрестками должна быть минимальной, тогда найден самый короткий путь.

Тебя видимо даже в ПТУ не взяли если ты так читаешь википедию.

Конечно нет, чё мне там делать. А тебя взяли?

Из всех узлов нужно выбрать тот расстояние от которого до наиболее удаленного от него узла минимально в сравнении с любым другим узлом.

Я чуть мозг не поломал, пока это дешифровал! Ты бы так и сказал, что тебе середину (центр тяжести) найти надо!

Как это сделать, не делая N+N*(N-1)/2 проходов, я не представляю.

белок же толкьо в зоопарк или на опыты

Прально, а желток съесть.

https://ru.wikipedia.org/wiki/Задача_о_кратчайшем_пути
и дальше по ссылкам, преподают это на первых курсах пту

А ещё там преподают что то что афтар спрашивал ___никак___ не относится к тому что ты ответил. Так что ПТУ-шники для тебя - недосягаемый уровень.

а почему ты вообще решил что такой узел единственный?

Ловите идиота!

Думаю что в общем случае быстро никак. Так или иначе, нужно считать расстояния между всеми вершинами, например, Флойдом-Уоршеллом. И потом выбирать центр.

Из всех узлов нужно выбрать тот расстояние от которого до наиболее удаленного от него узла минимально в сравнении с любым другим узлом.

Это как?

Флойдом-Уоршеллом

дешевле, как предлагали выше, запустить dfs от каждой вершины

порядка нескольких минут на моем компе

pentium pro? или java? или ты как-то иначе делал?

запустить dfs от каждой вершины

Его еще, кстати, попробуй реализовать! Ведь тут рекурсия не прокатит, итерациями нужно...

dfs не ищет кратчайший путь вообще-то

Потом такие как ты из этого ПТУ и рисуют маршрут по дороге с одностороннем движением в обратную сторону.

А про ориентированные графы ты не слышал?

Это как?

простыми словами, пусть у нас есть 1000 городов. Вопрос, в каком городе нужно жить чтоб из него можно было добраться наиболее быстро к самому дальнему.

Типа найти очень привлекательный город для туристов.

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

Просто так не отсортируешь, как точки на двумерной поверхности

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

1-2-3
|
4-5
|
6

Не очень хорошая эвристика

Это неверное предположение. Зато можно предположить, что наверняка наиболее удаленными от геометрического центра будут крайние узлы графа. Правда, толку от этого? Все равно перебирать все узлы замучишься!

Не очень хорошая эвристика

Я применил её к своей же идеей с городами. В столицу куча дорого(поезда, аеропорты и так далее). И теоретически из неё проще всего добраться в любой другой город.

НО! Это все разговор ниочем. Как сказал эдди алгоритм уже написан, так что дорога в гугл самая ближайшая))

Ведь тут рекурсия не прокатит

why not?

итерациями нужно

ну, итерациями можно и bfs сделать. да и dfs не сложнее

dfs не ищет кратчайший путь вообще-то

а нафига нам искать кратчайший путь?

хотя верно, dfs не катит. надо bfs

В общем случае задача комивояжера NP полна и точное решение будет очень медленным (а на 1000 городов вообще будешь считать 100500 лет). Так что делай примерное решение. Как именно - решай из конкретной задачи. Гугли на тему алгоритмы поиска пути.

Найдешь быстрое решение задачи комивояжера - обращайся в институт Клэя за своим заслуженным 1 000 000$

Ведь тут рекурсия не прокатит

why not?

Stack overflow. Какой у тебя размер стека? Ты миллион раз сможешь рекурсивно жирную функцию запустить?

а нафига нам искать кратчайший путь?

А на тот фиг, что тебе для начала надо будет между i-м узлом и всеми остальными узлами найти кратчайшие пути, а затем из найденных путей выбрать максимальный. И так для каждого узла. Затем взять минимум из полученного списка расстояний и получить k узлов, подходящих для твоей задачи.

Я вообще не представляю как можно облегчить эту задачу. Скажем, на паре миллионов объектов она считать будет целую вечность!!! Тут тебе в самый раз CUDA применить: распараллелить хотя бы на пару сотен потоков и считать группами (т.е., например, если у тебя 2млн узлов, то на видюхе с 200 ядрами GPU ты будешь на каждом ядре обрабатывать по 10тыс узлов).

Так как найти кратчайшее расстояние между двумя заданными узлами сложней, чем между одним заданным узлом и одним случайным, то, возможно, придется фактически для графа из N узлов составить N*(N-1) списков с кратчайшими путями между i-м и j-м узлом, память немного можно подсократить (до N*(N+1)/2), если учесть, что путь от i до j есть обратный путь от j до i.

После построения этого списка будет уже просто найти центр. Да и сами списки наверняка пригодятся для того, чтобы иметь возможность в дальнейшем «проложить маршрут» между узлами. Но не приведи Аллах тебе добавить/удалить хотя бы один узел: весь громоздкий расчет придется повторять!

быстрое

Для нашего времени это фантастика.

Ты бы так и сказал, что тебе середину (центр тяжести) найти надо

Ну да

простыми словами, пусть у нас есть 1000 городов. Вопрос, в каком городе нужно жить чтоб из него можно было добраться наиболее быстро к самому дальнему.

Да

Кстати, а нет ли графических способов решения этой задачи? Скажем, рисуем гигантскую простыню, на ней отмечаем узлы так, чтобы можно было явно нарисовать линию между двумя соединенными узлами. Если узлов немного (скажем, меньше uint16_t), то "картинка" будет 3*16-битной: на первой плоскости нулем обозначим фон, остальные цифры — номер узла + 1; на второй и третьей плоскости нарисуем линии "цветом" соединенных узлов (скажем, если у нас узлы 3 и 20 соединены, мы между ними проводим линию в плоскости 2 "цветом" 3, а в плоскости 3 "цветом" 20).

Далее, чтобы найти кратчайшее расстояние между узлами, проводим на нашей картинке между ними прямую и смотрим, какие связи она напересекает, если никаких, то расширяем эту линию (диляция), пока не пересечет чего-нибудь. А потом начинаем через найденные связи строить траектории (тоже диляцией), подбирая набор ломаных.

Да, все равно долго получится...

а затем из найденных путей выбрать максимальный

Скорее решением будет узел с минимальной суммой длин путей до остальных узлов

центр тяжести
центр

Внезапно первый же результат в гугле по «центр графа»

http://www.uchimatchast.ru/teory/center.php

http://rain.ifmo.ru/cat/data/theory/graph-location/centers-2006/article.pdf

смотрю здесь погромисты собрались в товарных количествах...

решается с кубической сложностью в рамках курса дискретной математики технического вуза (тебе правильно сказали насчёт флойда-уоршелла). можно плясками с бубном несколько уменьшить сложность.

Из ОП-поста вроде бы предельно ясно, что автора интересует задача поиска центра графа. Но анонимуса было не остановить в его стремлении нести знание людям!

В общем случае задача комивояжера NP полна

Продолжайте наблюдения, коллега.

Это другая задача, которая называется «размещение медиан в графе».

Stack overflow. Какой у тебя размер стека? Ты миллион раз сможешь рекурсивно жирную функцию запустить?

Цивилизация с планеты Земля давно изобрела TCO.

Можно отрезать все листья. Потом опять. И так, пока задача не станет тривиальной.

*--*
|  |
*--*

Приступай к обрезке листьев.

Можно отрезать все листья. Потом опять. И так, пока задача не станет тривиальной

красавчик

Хм. Да, чот затупил, ведь «каждый узел которого связан с несколькими другими узлами».

токой вершины может и не быть! Решение с O(N^2) сложностью (для графов с положительными ребрами): 1. для каждой вершины выбираем ребра с минимальной длиной. 2. обьединяем множества 3. PROFIT

токой вершины может и не быть!

Только если весь твой граф — цикл. И то, здесь правильно говорить не "не быть", а "все вершины".

Графы. Размещение центров. ©

Можно отрезать все листья. Потом опять. И так, пока задача не станет тривиальной.

Да, именно так эта задача и решается.

В качестве центра могут остаться две вершины, это абсолютно нормально.

смотрю здесь погромисты собрались в товарных количествах

решается с кубической сложностью

Лол, решается с линейной сложностью, погромист ты наш.

Обожаю CS-треды на ЛОРе. :] Тут уже и NP-полноту кто-то успел упомянуть.