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

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

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

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

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

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

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

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

0+10 (0)

0+ 0  (0)

0 +0  (0)

8+6   (14)

0+0   (0)

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

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

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

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

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

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

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

Итак: небольшой фрагмент кода на языке 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();
                                   }                     
            }
 

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