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

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

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

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

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

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

От уже из наших товарисчей-компуторщиков никто ничего и не понял. А то ли ещё будет!:-)

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

никто ничего и не понял

Поэтому, задания с ним очень любят преподаватели вузов.

:) 

Форматирование кода поправить бы. А так - уже в "волне" все высказались. Разницы нет. 

Да, и называть переменные на русско-английской "трасянке" (типа и MatricaVesov, и MatrixTop) - не комильфо. Плохой стиль. 

Хотите транслитом для доступности - называйте уж все транслитом. Но реально (в приличных исходниках) такого (транслита) я не припомню. 

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

Никто ничего не понял.

А что тут понимать? Нам эту хрень читали. :) У меня даже в дипломном проекте было. И давно применяется практически; автор, погуглите, где и как. Это было бы интереснее упражнений в вышивании крестиком. :))

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

Это было бы интереснее упражнений в вышивании крестиком. :))

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

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

Я хочу работать с алгоритмами и буду писать о них.

Да кто ж запрещает.

реализуйте ваши гениальные идеи сами.

Сорри, не хотел обидеть; лишь высказал мнение.

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

Сорри, не хотел обидеть; лишь высказал мнение.

Да я и не обиделся. Просто, журналистика мне давно скучна и неинтересна. И предложения о чем то там написать, если они не исходят от редакции, огорчают. Так и хочется сказать: "Сначала выпишите чек".

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

Не лезьте в бутылку. Вам никто ничего не предлагал. Вы сами запостили 1-ый коммент, :) полагаю, от невнимания публики к опусу. Я лишь высказал мнение о его интересности. И всё.

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

Я лишь высказал мнение о его интересности. И всё.

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

Надеюсь, посыл понятен? 

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

Посыл понятен: Вы стали вещать за всю публику: "Кроме вас никто всё равно ничего не понял".

:)   :))   :)))

Пожалуйста, не говорите за всех. Почти любому технарю и/или экономисту в ВУЗе это читали. В гуманитарках, конечно, вряд ли, но и тут я бы не стал утверждать 100%-но.

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

Почти любому технарю и/или экономисту в ВУЗе это читали. 

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

Пожалуйста, не говорите за всех.

За всех я и не говорил

В гуманитарках, конечно, вряд ли, но и тут я бы не стал утверждать 100%-но.

:-) Какие гуманитарки, о чем вы, вообще? Чудак вы...:-)

Страницы