Ищем кратчайшие пути: Алгоритм Шимбелла

Данная статья о сложном алгоритме поиска маршрута в графах. К слову, графы не только труднее для понимания, но и необычны для визуального восприятия. Правда, только сначала. А речь пойдет сегодня об алгоритме Шимбелла.

Нашей главной задачей будет найти кратчайший путь. Но сам путь уже будет другим. Вот так (см. рис) выглядит ориентированный граф.

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

На основе графы строится матрица. Эта матрица отображает расстояния между доступными вершинами графа. Она называется матрицей весов.

На графе по стрелкам направлений видно, что мы можем попасть из четвертой вершины графа в пятую и обратно тоже. А вот из второй вершины можно попасть в пятую, а обратно — никак. Соответственно, заполняются и поля матрицы. Если прохода нет, мы пишем 0.

Матрица весов

0

1

2

3

4

5

1

0

10

0

0

0

2

0

0

12

0

8

3

0

0

0

8

0

4

0

6

8

0

3

5

0

0

0

3

0

Одно из математических решений таких задач — алгоритм Шимбелла, основанный на хитром сложении матриц. В чём его хитрость? Чтобы узнать путь кратчайший путь от одной вершины к другой из двух рёбер, мы складываем поочередно каждый элемент соответствующей номерам вершин строки и столбца. Причем операции, где фигурирует хотя бы один ноль, мы игнорируем. А из получившихся при сложении пар элементов кратчайших цифр выбираем наименьшую. Представить граф очень просто — вообразите себе сеть дорог с блок-постами, где-нибудь на Донбассе или в Сирии. Вполне могут сложиться ситуации, когда одни посты будут закрыты, другие получат приказ пропускать беженцев только в одну сторону, а с третьих их охрана, вообще, сбежит, оставив свободный путь. Вот вам и ориентированный граф. Матрица весов будет основным инструментом, с которым нам предстоит работать.

Итак, путь от элемента 3 к элементу 2.

0+10 (0)

0+ 0  (0)

0 +0  (0)

8+6   (14)

0+0   (0)

Единственная операция, которая удовлетворяет нашим условиям, дает 14. Теперь посмотрите на рисунок в самом верху – единственный кратчайший путь из двух ребер от вершины 3 к вершине 2, через 4-ю имеет вес 14. На матрице для кратчайших путей из двух ребер, изображенной ниже.

Матрица для кратчайших путей из двух ребер   

0

1

2

3

4

5

1

0

0

22

0

18

2

0

0

0

11

0

3

0

14

0

0

11

4

0

0

18

0

14

5

0

9

11

0

0

 

Алгоритм кажется несколько сложным, но на самом деле это очень примитивная арифметика. А уж программируется она и вовсе несколькими строчками, если не «рисовать» визуальный интерфейс. Но… крепко подумать при этом всё же придется, если подзабыты правила работы с двумерными матрицами.

Я решил не напрягать вас и разработал элементарное решение. В первом приближении нам нужно в двойном цикле пройти все элементы двумерного массива. Нужен и третий цикл внутри двух первых, который будет на каждом шаге складывать элемент искомых строки и столбца. 

При этом нужно создать простейший набор условий, который поможет нам отбросить операции, где фигурирует хоть один ноль, и операции с одинаковыми номерами строки и столбца (см. пример: элемент с адресом 3.4 просчитать можно, а вот 3.3 – это вершина 3. А из вершины 3 мы не можем пройти в вершину 3, мы уже там находимся).

При вычислении матрицы для путей из трех ребер необходимо будет складывать элементы строки и столбца первой и второй полученной матриц. В самом алгоритме изменятся только слагаемые. Переписывать его уже не потребуется.

0

1

2

3

4

5

1

0

0

0

21

0

2

0

17

19

0

23

3

0

0

26

0

22

4

0

12

14

17

19

5

0

0

21

0

17

Алгоритм Шимбелла — далеко не самый эффективный, с точки зрения расхода памяти и скорости выполнения вид поиска кратчайших граней но он весьма полезен с точки зрения понимания работы циклов и условий. Поэтому, задания с ним очень любят преподаватели вузов.

 

Итак: небольшой фрагмент кода на языке Java, который обеспечивает поиск кратчайших путей из двух и трех ребер графа. Код работает, его можно использовать для создания собственных методов, классов и решения лабораторных работ.

public class Shim {
            public static void main(String[] args) {
                        // TODO Auto-generated method stub
 
                        int n = 5;
                        int v = 0;
                        int i = 0;
                        int l = 0;
                        int f = 0;
                        int j = 0;
                        int w = j;
                        int [][] MatricaVesov = {{0,10,0,0,0},{0,0,12,6,8},{0,0,0,8,0},{0,0,0,0,3},{0,3,0,3,0}};
                                  
                                   int [][] Matrix2Top = new int [n][n];
                                    int [][] Matrix3Top = new int [n][n];
                                                                      
                                   System.out.println("Матрица весов первой степени степени");
                                   for (i = 0; i < n; i++){
                                               for (j = 0; j < n; j++){
                                                           System.out.printf("%3d", MatricaVesov[i][j]);
                                               }
                                               System.out.println();
                                   }                                             
           
                                   for (i = 0; i < n; i++){
                                               for (j = 0; j < n; j++){
                                                           f = i;
                                               w = j;
                                                           for (l = 0; l < n; l++)    {
                                                                                                                     
            v = MatricaVesov[i][l] + MatricaVesov[l][j];
if(MatricaVesov[i][l] != 0 && MatricaVesov[l][j] != 0&&MatricaVesov[i][l]!=MatricaVesov[l][j]) {
                                                                       Matrix2Top[i][j] = v;
                                                           }
                                               }
                                   }
                                   }
                                   System.out.println();
                                   System.out.println("Матрица весов второй степени");
                                   System.out.println();
                                   for (i = 0; i < n; i++){
                                               for (j = 0; j < n; j++){
                                                           System.out.printf("%3d", Matrix2Top[i][j]);
                                               }
                                               System.out.println();
                                   }                     
                                  
                                   for (i = 0; i < n; i++){
                                               for (j = 0; j < n; j++){
                                                           f = i;
                                               w = j;
                                                           for (l = 0; l < n; l++)    {
                                                          
                                                                      
            v = MatricaVesov[i][l] + Matrix2Top[l][j];
if(MatricaVesov[i][l] != 0 && Matrix2Top[l][j] != 0&&MatricaVesov[i][l]!=Matrix2Top[l][j]) {
                                                                       Matrix3Top[i][j] = v;
                                                                      
                                                                       }
                                               }
                                   }
                                   }
                                   System.out.println();
                                   System.out.println("Матрица весов третьей степени");
                                   System.out.println();
                                                                       for (i = 0; i < n; i++){
                                               for (j = 0; j < n; j++){
                                                           System.out.printf("%3d", Matrix3Top[i][j]);
                                               }
                                               System.out.println();
                                   }                     
            }
 

Эдуард Трошин

Версия для печатиВерсия для печати

Рубрики: 

  • 1
  • 2
  • 3
  • 4
  • 5
Всего голосов: 0
Заметили ошибку? Выделите ее мышкой и нажмите Ctrl+Enter!

Читайте также

Комментарии

Страницы

Аватар пользователя Petro45

но упрётесь в тупик - нет визуализации, не считать же визуализацией вызов методов типа:

Да вы что, есть в Java визуализация, и серверная и под любую ось. Только это не для новичков код, как и в вашем примере с JS. 

Открою секрет: Ессли бы вы раскрыли свой широкий "лопатник", кинули бы на кон десяток зеленых сотенных бумажек, я, быть может и задумался над тем, как и что можно визуализировать, а так, как вы просто, извините за выражение, обычный бол..тун (если не сказать больше), то мне эта дискуссия неинтересна. Яволь?

petro45 >Да вы что, есть в Java визуализация, и серверная и под любую ось.

Петро, не тормозите, я про визуализации в броузере, чтобы обычный юзер смог за пару секунд посмотреть на результат!

А этого в настоящее время можно достичь только и только с помощью Javasсript.

Всё остальное - паллиативы. Или по простому - костыли!


Аватар пользователя Petro45

Петро, не тормозите, я про визуализации в броузере, чтобы обычный юзер смог за пару секундпосмотреть на результат!

Да чушь это, не нужен юзеру этот результат, если он не умеет алгоритмы писать. Ни к чему ему эти картинки. Это все в командной строке можно нарисовать и распечатать. Новичок должен уметь писать коды, а рассматривая картинки этому не научишься.  

Я не пойму, чего-вы добиваетесь-то? Я не буду ваш JS изучать и создавать визуальные уроки.  Тем более, что и вы сами этого JS не знаете но почему-то пиарите.

А как человек, проводивший занятия по программированию в начальных группах, могу сказать точно, что вначале необходимо прочно освоиться в командной строке. Яволь? 

petro45 > Да чушь это, не нужен юзеру этот результат, если он не умеет алгоритмы писать. Ни к чему ему эти картинки. Это все в командной строке можно нарисовать и распечатать. Новичок должен уметь писать коды, а рассматривая картинки этому не научишься. 

Лео вас бы "ногами забил" за такое пренебрежение к визуализации результата математического. Имхо.

petro45 > могу сказать точно, что вначале необходимо прочно освоиться в командной строке. Яволь?

Да, я знаю про линуксоидов.

Аватар пользователя Petro45

Да, я знаю про линуксоидов.

Это хорошо, только о программировании вы, похоже, понятия не имеете. Как и о JS в частности. Впервые встречаю такого странного демагога, который пишет о том, чего не знает.

petro45 > Это хорошо, только о программировании вы, похоже, понятия не имеете.

А мне нравится ваш текст (стиль) когда вы пишете не о ... программировании.

Писать просто текст у вас талант. Имхо.

Smile

Кстати, а вот чувак, который работает программистом, но страсть имеет к писанию:

"К чему же я испытываю настоящую страсть?

Писательство. Писательство, можно сказать, моя самая главная страсть в жизни. Я писал короткие рассказы со второго класса. Я писал комиксы, скетчи, повести, романы, документальные книги, блоги и многое другое. На самом деле, за исключением работы, писательство — это тот мир, где я провожу большую часть своего времени!

Привычка писать — основная причина того, что я поддерживаю свой блог. Совсем не из-за страсти к разработке, а именно к писательству. Но литературное творчество недостаточно оплачивается, а писательский труд не вдохновляет (по крайней мере меня). Я не могу представить себя в роли литературного раба для кого-то, кто не заботится о содержании; в качестве копирайтера для журналов, которые меня не интересуют, или нытика, пытающегося найти высокооплачиваемую работу. Это такая область, которая видится мне гораздо худшим компромиссом, если сравнивать с программированием.

Однако, не могу сказать, что не поменял бы деятельность, если бы представилась хорошая возможность. Если бы одна из моих книг, которую я издал сам, попала бы в список 100 лучших на Амазоне, и издатель вышел со мной на контакт, я бы уцепился за эту возможность. Если бы в один прекрасный день, я нашёл настолько убедительную историю, что захотел бы создать какую-то уникальную интерактивную книгу, я бы представил это на Кикстартере и попытался бы получить финансирование. Черт, если бы мне так повезло, как Э. Л. Джеймс (она же Эрика Леонард, автор книги «Пятьдесят оттенков серого»), я бы не сомневаясь ушёл из программирования. Я бы продолжил писать код, но опять же, только потому, что программирование скорее для меня основное хобби. Я бы свободно перешёл работать в любую область, касающуюся моих других увлечений, если бы у них были те же преимущества (и кто знает, может я так и поступлю): музыкальная индустрия, концептуальный дизайн, маркетинг, игры, фотография и т.д.

Страсть немного отличается от хобби. Страсть к чему-то предполагает стремление к величию, к движению вперёд и совершенствованию. К получению самоудовлетворения от собственных усилий. Хобби это то, чем вы занимаетесь в нерабочее время — это отдых или просто какая-то деятельность, для разнообразия..."

Аватар пользователя Petro45

А зачем вы сюда копируете это? Мне наплевать на то, что там на душе у этого чела. Меня не интересует писательство,я 20 лет им занимался. И все, что я получал - 10 долларов к зарплате, раз в полгода, в качестве гонорара и лишнюю рюмку коньяка на презентации.

Я должен был вкалывать на двух работах, а по ночам - охранять склады за городом, чтобы заработать копейку. А этот осёл из вашего отрывка лениво рассуждает о том, что он стал бы делать, а чего не стал бы. Это чушь, да и сам он - мудак.

А вы его зачем-то копируете и что-то там равняете. Вы-то, вон, даже и написать-то не можете - вам надо чужое скопировать. 

petro45 >А зачем вы сюда копируете это?

А вы зеркальная копия его. Имхо.

ЗЕРКАЛЬНАЯ!!!!

Аватар пользователя Petro45

ЗЕРКАЛЬНАЯ!!!!

Бред

Страницы