Консультация № 109720
16.11.2007, 16:58
0.00 руб.
0 2 2
помогите пожалуйста решить задачку

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

Обсуждение

Неизвестный
16.11.2007, 22:27
общий
это ответ
Здравствуйте, Potapp!
Насколько я помню, алгоритм Дейкстры ищет минимальный путь между узлами.
А нужно найти минимальную сумму расстояний - город, с которого самые короткие пути во все остальные.
Можно задачу решить перебором.
Нужно составить матрицу расстояний.
X1 X2 X3
X1
X2
X3
на главной диагонали поставить 0.
тогда вся задача сводится к нахождению минимальной суммы строк или столбцов (матрица будет зеркальной)
Неизвестный
17.11.2007, 10:55
общий
это ответ
Здравствуйте, Potapp!
<a href=http://www.rambler.ru/srch?set=www&words=%C7%E0%E4%E0%F7%E0+%EA%EE%EC%EC%E8%E2%EE%FF%E6%E5%F0%E0&btnG=%CD%E0%E9%F2%E8%21>Link...</a>
или любой другой поисковик.
Запрос: "Задача коммивояжера"<p><fieldset style=‘background-color:#EFEFEF; width:80%; border:#777777 1px solid; padding:10px;‘ class=fieldset><font color=#777777><i>Исправлена длинная ссылка.</i>
-----
</font><font color=#777777 size=1><b>• Отредактировал: <a href=/info/user/14422 target=_blank>Gh0stik</a></b> (Профессор)
<b>• Дата редактирования:</b> 17.11.2007, 11:41</font></fieldset>
Форма ответа