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

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

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

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

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

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

Комментарии

Страницы

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

Чего на Петро набросились:).... Он в принципе неплохое дело делает. По крайней мере, какое-то знание пропагандирует. Пишет неплохо, хотя и, ясное дело, по-своему немного. Задачи на графах - важная область для ИТ, особенно близкого к каким-то настоящим серьезным научным разработкам. Конечно, он не систематически знаком с темой (это чувствуется по тексту), но обладает цепким умом, мотивацией, любознательностью. А это, имхо, хорошо. Кто-то прочитает, а потом, глядишь, и книжку откроет, что уже само по себе - хорошо. По сути статьи, я бы нагнал больше журнализма - ибо тема позволяет. Я бы, наверное, про мыльные пленки, например, написал (это задачка по поиску оптимальной сети близкая).

leo3 >Чего на Петро набросились:).... Он в принципе неплохое дело делает. По крайней мере, какое-то знание пропагандирует. Пишет неплохо, хотя и, ясное дело, по-своему немного... я бы нагнал больше журнализма...

Так за отсутствие этого самого  "журнализма" то он и отгребает то тут! Имхо.

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

За отсутствие этого самого  "журнализма" то он и отгребает то тут!

Именно. Лучше на простеньком, но реальном примере показать, что даёт решение задачки, чем устраивать jobation.

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

По сути статьи, я бы нагнал больше журнализма - ибо тема позволяет.

Спасибо, учту...

Лучше на простеньком, но реальном примере показать, что даёт решение задачки, чем устраивать jobation.

Серьёзный пример займет слишком много места и в нем будет много лишнего для новичка...

но обладает цепким умом, мотивацией, любознательностью.

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

Вот, говорили мне: не сумеешь освоить за полгода - кидай. Я не послушал. 


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

Петро - не раскисать! Молодец! Правильно все! Пиши! Зачем... кинь эти дурацкие вопросы:) Чел., который писать умеет, должен писать.

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

Чел., который писать умеет, должен писать.

А что ж сами-то забросили? :) Я по вас соскучился. Честно.

Петро всё прочувствовал и поделился, что вышло. Пользы от его статей побольше, чем от опусов "про чёрные ящики". Конкретики б чуток -- цены бы не было.

Страницы