Знаходження найкоротшого шляху між будь-якими двома вершинами графа матричним методом

Для розв'язання задачі ми будемо використовувати символ . Для спрощення розгляду припустимо, що всі цілі числа менше , так що для кожного додатнього цілого числа та . Приймемо також, що . Це - для зручності позначень.

Для поліпшення системи позначень використовується наступне визначення.

Визначення. Нехай й — матриці-рядка, де кожне з й — ненегативні цілі числа або . Тоді .

Визначення. Нехай — число, а матриця-

рядок. Тоді .

Задача 2. Задано граф. Необхідно визначити найкоротшу відстань між будь-якими двома вершинами графа.

Рішення. Застосуємо алгоритм Флойда-Уоршолла. Нехай — матриця, де — вага ребра якщо ребро існує й у противному випадку. У нашому випадку

.

Знайдемо вагу всіх шляхів довжини 2, або 2-шляхів, у яких середньою вершиною є вершина . Починаємо з першого стовпця. Знаходимо перший рядок у першому стовпці, у якій є позитивне ціле число. У цьому випадку це число 2 у другому рядку. Таким чином, існує ребро з вершини до вершини . вагою 2. Якщо в першому рядку на позиції є ціле число , то існує ребро з вершини до вершини вагою . Тоді — вага 2-шляху з вершини у вершину . Таким чином, якщо додати 2 до кожного елемента в першому рядку, то одержимо рядок, яку варто розглядати як матрицю-рядок, позначаючи її , так що — вага шляху довжини 2 з вершини до вершини . Якщо розглядати , другий рядок матриці як матрицю-рядок, тоді . — вага шляху довжини 1 з вершини до вершини . Оскільки нас цікавить найкоротший шлях для кожного , заміняємо другий рядок матриці на . Аналогічним образом, у четвертому рядку першого стовпця перебуває число 3, тобто існує ребро з вершини - до вершини вагою 3. Якщо в першому рядку на позиції є ціле число , то існує ребро з вершини , до вершини вагою . Тоді — вага 2-шляху з вершини до вершини . Отже, якщо додати 3 до кожного елемента в першому рядку, то одержимо рядок, яку варто розглядати як матрицю-рядок, позначаючи її , так що — вага 2-шляху з к. Якщо розглядати четвертий рядок матриці як матрицю-рядок, тоді — вага шляхи довжини 1 з к. Оскільки нас цікавить найкоротший шлях для кожного , заміняємо четвертий рядок матриці на . І тому що в інших строкаx першого стовпця більше немає позитивних цілих чисел, перший етап завершений, у результаті якого маємо

.

Тепер розглянемо другий стовпець матриці . Якщо в -тім рядку другого стовпця є число , то існує ребро з вершини до вершини вагою . Якщо в рядку на позиції є ціле число , то існує ребро з вершини до вершини вагою . Тоді — вага шляху з к. Отже, якщо додати число до кожного елемента в другому рядку, то одержимо рядок, яку варто розглядати як матрицю-рядок, позначаючи її , так що — довжина 2-шляху з вершини к. Якщо розглядати , -тую рядок матриці як матрицю-рядок, тоді — довжина шляхи з вершини к. Оскільки нас цікавить найкоротший шлях для всіх , заміняємо -тую рядок матриці на . У другому стовпці є число 2 у першому рядку, число 4 із третьому рядку, число 5 - у четвертому рядку й число 1- у п'ятому рядку. Використовуючи цей процес для кожного з наступних рядків, отримаємо

Розглянемо тепер третій стовпець матриці . Для кожної позиції матриці на якій є позитивне ціле число, додаємо це число до третього рядка матриці , одержуючи матрицю-рядок , після чого покладемо рівної -ой рядку матриці . Далі заміняємо -у рядок матриці на й одержуємо

.

Тепер розглянемо четвертий стовпець матриці . Для кожного позитивного елемента на позиції матриці додаємо це значення до четвертого рядка матриці , щоб одержати й покласти рівної -ой рядку матриці . Далі заміняємо -у рядок матриці на й одержуємо

.

Нарешті, розглянемо п'ятий стовпець матриці . Для кожного позитивного елемента на позиції матриці додаємо це значення до п'ятого рядка матриці одержуючи й думаємо рівної -ой рядку матриці . Далі заміняємо -у рядок матриці на одержуємо

.