Определение кратчайших путей на графе.
Учебные материалы


Определение кратчайших путей на графе.



Карта сайта whitebis.ru

Каждая матрица смежности ||R|| графа дает число путей длины 1 между парой вершин xi и yi. Длина пути – число дуг в пути.

Аналогично, в клетках матрицы ||R||2 содержится количество путей между вершинами xi и yi, имеющих длину 2.

В общем случае, матрица ||R||r дает число путей длины

r

между парой вершин (xi,yi).

R1= R2=

Пример.

R3= R4=

Произведение матриц A(m,n) * B(n,k) = C(m,k) , где

сij= ai*bj

║3 -1 ║ ║ 5 -2 ║ ║ 3*5-1*4 -3*2-1*3 ║

║2 5 ║ * ║ 4 3 ║ = ║ 2*5+5*4 -2*2+3*5 ║

║1 -4 ║ ║ ║ ║ 1*5-4*4 -1*2-3*4 ║

(3,2) (2,2) (3,2)

Определение кратчайших путей на графе.

Решение этой задачи м.б. рассмотрено на задачах поиска кратчайшего выхода из лабиринта.

Для решения строится граф лабиринта. Перекрестки и концы тупиков отмечаются как вершины, а коридоры как ребра.

На построенном графе производится разметка его вершин следующим образом: вход лабиринта (x1) отмечается меткой «0». Все вершины, смежные с отмеченной, отмечаются «1». Далее все вершины, смежные с отмеченными меткой «1», получают метку «2» и т.д., пока не будет отмечен выход.



Кратчайший путь ищется так: берется выход и ищется вершина, смежная с ним и с меткой, на единицу меньше. Аналогично действуем до тех пор, пока не дойдём до входа.



edu 2018 год. Все права принадлежат их авторам! Главная