Алгоритмы Шимбелла и Дейкстры

Не думайте, что мне было скучно и я просто так решил запрограммировать данные алгоритмы. Эта задача была поставлена в лабораторной работе курса «Основы навигации», вот и пришлось делать, но это первая интересная тема была из всего семестра  🙂 Так вот данные алгоритмы позволяют найти кратчайшие расстояния или лучшие пути между двумя городами. Собственно это не определение этих алгоритмов, а практическое их применение. Теорию по алгоритму Дейкстры я описывать не буду (если надо, скажите — напишу). А вот за Шимбелла пару слов скажу.

И так, пусть у нас будет  граф представленный на рисунке выше, где стрелочками я обозначил возможные направления движения от вершины. Обратите внимание, что из вершины 2 мы не можем двигаться в вершину 1. Составим матрицу весов:

1 2 3 4
 1  0  10  15  5
 2  0 0  20  0
 3  15 20  0  0
 4  5  0  0  0

Вот, эта матрица, матрица первой степени, отображает кратчайшие расстояния из одного ребра  между вершинами (если ехать из пункта 1 в пункт 2 по одной дороге, то расстояние 10, а вот если ехать из пункта 2 в пункт 4, то расстояние равно 0, так как прямой дороги нет). Если возвести полученную матрицу во вторую степень, то получим кратчайшее из двух ребер, если возвести в третью степень — из трех ребер и т.д.. Давайте возведем полученную матрицу во вторую степень.

Только следует отметить, что тут надо работать по особому алгоритму, не просто умножение строки на столбец. И так давайте получим элемент (2,3) нашей матрицы.  Берем вторую строку и третей столбец, только знак умножения заменяем на знак сложения 0+15, 0+20, 20+0, 0+0. Зачеркиваем все слагаемые, которые содержат ноль — то есть в нашем случае — все. И так, получаем элемент (2,3), который равен нулю. Если посмотреть на наш граф, то да, видно, что нельзя в вершину 3 попасть по двум граням. Найдем элемент (1,3):  0+15, 10+20, 15+0, 5+0, отбрасываем все суммы, где есть хоть одно слагаемое равное нулю, остается только 10+20, складываем, получается 30.

1 2 3 4
 1 10 35 30 0
 2 35 40 0 0
 3 0 25 30 20
 4 0 15 20 10

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

В предыдущих примерах, когда мы опускали суммы, где есть ноль, оставалась только одна сумма, либо вовсе ничего. А вот если было бы например так 10+15, 10+20, 15+3, 5+0. То просто в конце выберем минимальный результат. Опускаем суммы с нулям: 25,  30, 18. Минимальный результат — 18.

1 2 3 4
 1 45 20 25 15
 2 0 45 50 40
 3 25 50 45 0
 4 15 40 35 10

Теперь давайте получим матрицу 3-й степени (кратчайшее расстояние из 3 ребер/дорог), для этого мы умножим матрицу первой степени на матрицу второй степени. Получим элемент (3,1). Берем 3-ю строку матрицы первой степени умножаем на 1-й столбец матрицы  второй степени: 15+10, 20+35, 0+0, 0+0 -> 25, 55 -> 25. Теперь элемент (2,1): 0+10, 0+35, 20+0, 0+0 ->0. И так далее, в итоге получаем результат изображенный в таблице слева.

По поводу алгоритма Дейкстры ! Решение с помощью данного алгоритма представлено в виде матрицы по центру окна программы. Первая строка матрицы — это кратчайшее минимальное расстояние от первой вершины к остальным. Вторая — от второй вершины к остальным. А матрица на синем фоне — исходная матрица загружаемая из файла file.txt.

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

result


  • qwerty

    Вы с ХАИ?

    • Совершенно верно!