Дан неориентированный граф. Для простоты будем считать, что если между 2 вершинами существует ребро, то расстояние между этими вершинами равно единице. Заданы начальная и финальная вершины. Найти кратчайшее расстояние между заданными вершинами можно легко с помощью классического обхода в ширину. Но возникает следующий вопрос : как найти количество этих кратчайших путей в графе?

задан 28 Июл '16 21:17

изменен 28 Июл '16 21:17

Если мы знаем расстояние, то есть длину кратчайшего пути между вершинами i, j, и оно равно d, то достаточно рассмотреть d-ую степень матрицы смежности графа. Элемент с координатами (i,j) матрицы A^d покажет число путей длины d от i до j; все они являются кратчайшими.

(28 Июл '16 21:23) falcao

@falcao, а почему именно так? Как то не совсем очевидно... А если расстояния между вершинами будут вещественные величины?

(28 Июл '16 21:54) garex

@marka_17: то, что количество путей данной длины вычисляется через степени матриц -- это довольно простой факт. Он есть в учебниках. Можете посмотреть книжку Р.Уилсона.

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

(28 Июл '16 22:17) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×674
×291

задан
28 Июл '16 21:17

показан
1408 раз

обновлен
28 Июл '16 22:17

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru