Поиск кратчайших путей в графе методом Форда-Беллмана

 

Пример

Рассмотрим пример работы метода Форда-Беллмана. Для наглядности  используем графическое задание  графа.

Шаг 1. Задаем граф: пронумеруем  вершины (№1 присвоим стартовой вершине); укажем направления и веса ребер.

 

 

 

 

 

 

 

 

 

 

 

 

 

Шаг 2: Пусть расстояние для  каждой вершины (кроме стартовой) равно  бесконечности.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Шаг 3: Проведем релаксацию ребер  для каждой вершины, начиная с 1, сравнивая  уже имеющийся кратчайший путь с  суммой (d[a]+c_b) c d[b], где a – рассматриваемая вершина, c_b – расстояние от вершины а до смежной вершины b, d[b] – текущее значение кратчайшего пути до b. Рассматриваемое ребро будем выделять красным цветом; ребро, входящее в кратчайший путь будем выделять белым.

Шаг 4. Кратчайшие пути найдены, теперь пройдемся по графу еще раз  для проверки на наличие в нем  отрицательных циклов.

 

Шаг 5: В графе нет циклов отрицательного веса. Работа алгоритма  закончена.

 

 

 

 

 

 

 

 

Разработка ПО

n – количество ребер, s – номер стартовой вершины, z – флаг на наличие отрицательных циклов в графе (1 – нет, 2 – есть), konst – максимально допустимое количество ребер в графе, k - счетчик количества ребер

int[] a - массив начал ребер

int[] b - массив концов ребер

int[] w - массив весов ребер

int[] d - массив расстояний

 

начало

Для того, чтобы облегчить  построение приложения, реализующего алгоритм Форда-Беллмана, составим блок-схему (использован синтаксис C#):

 

   Int n, s, m, k=1, konst;

  int[] a = new int[konst];

  int[] b = new int[konst];

int[] w = new int[konst]; int[] d = new int[konst]; 

 

 

 

Здесь идет заполнение массивов, содержащих параметры ребер. Цикл i идет по вершинам графа (от 1 до n).

i=1

i<=n

нет

да

 

m – количество ребер, идущих ИЗ i-й вершины.

d[s] = 0

i++

di] = MAX

i<=n

i=1

нет

да

i++

k++, j++

b[k], w[k]

a[k] = i

j<=m

j=1

m

да

нет

 

 

Происходит первичное заполнение массива расстояний.

 

Для каждого ребра указывается  конечная вершина и вес.

 

 

 

 

 

 

 

 

i=1

 

Основная часть программы  – сам алгоритм Форда-Беллмана

да

нет

i<=n

 

j=1

да

нет

j<=k

d[b[j]] > (d[a[j]] + w[j])

да

d[]

нет

Для каждого ребра из массива  ребер происходит сравнение текущего кратчайшего расстояния до конца  ребра с суммой (текущее кратчайшее расстояние до начала ребра + вес ребра) и попытка улучшить кратчайшее расстояние до конца ребра

Вывод массива расстояний

 

i++

d[b[j]] = d[a[j]] + w[j]

конец

j++

 

 

 

 

 

 

 

 

 

 

Листинг программы

int n, s, m, k=1, z=1, konst = 20; // n – количество ребер, s – номер стартовой вершины, z – флаг на наличие отрицательных циклов в графе (1 – нет, 2 – есть), konst – максимально допустимое количество ребер в графе, k - счетчик количества ребер

int[] a = new int[konst];         // массив начал ребер

int[] b = new int[konst];         // массив концов ребер

int[] w = new int[konst];         // массив весов ребер

int[] d = new int[konst];         // массив расстояний

 

Console.WriteLine("Введите количество вершин:");

n = int.Parse(Console.ReadLine());       // Количество вершин

 

Console.WriteLine("Введите номер стартовой вершины:");

s = int.Parse(Console.ReadLine());        // Стартовая вершина

 

for (int i = 1; i <= n; i++)              // Задание массивов ребер

{

        Console.WriteLine("Введите количество ребер, исходящих из вершины " +i);

             m = int.Parse(Console.ReadLine());

             for (int j = 1; j <= m; j++)

              {

               a[k] = i;

                          Console.WriteLine("Введите номер конечной вершины для "+ j + "-го ребра, исходящего из "+ i+ ":");

                          b[k] = int.Parse(Console.ReadLine());

                          Console.WriteLine("Введите вес "+ j+ "-го ребра, исходящего из "+ i+ ":");

                          w[k] = int.Parse(Console.ReadLine());

                          k++;

                    }

       }

    

for (int i = 1; i <= n; i++) d[i] = 999999;

d[s] = 0; // заполнение массива расстояний перед началом работы алгоритма

 

for (int i = 1; i < n; i++)     // собственно, алгоритм

{

        for (int j = 1; j < k; j++)

              {

                     if (d[b[j]] > (d[a[j]] + w[j]))

d[b[j]] = d[a[j]] + w[j];                                  

                    }   

                       

       }

 

for (int j = 1; j < k; j++)    // проверка на наличие цикла с отрицательным весом

{

        if (d[b[j]] > (d[a[j]] + w[j]))

                    {

                        z = 0;

                        break;

                    }

      }   

 

if (z == 0)         // вывод

       {

        Console.WriteLine("Граф содержит цикл отрицательного веса");

                  

       }

else for (int i = 1; i <= n; i++)

if (d[i] == 999999)

        {

              Console.WriteLine("Кратчайшего пути до вершины " + i + " не существует.");

             }

       else if (i != s)

        {

             Console.WriteLine("Кратчайший путь до вершины " + i + " = " + d[i]);

             }

Console.ReadLine();

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

В данной курсовой работе рассмотрены  основные алгоритмы, решающие задачу поиска кратчайших путей в графе. Приведен пример решения данной задачи по алгоритму  Форда-Беллмана и блок-схема для  реализации алгоритма в программе. Результатом работы стало создание консольного приложения на языке программирования C#, реализующего алгоритм Форда-Беллмана (исходный код программы и сама программа есть на CD-диске, прилагаемом к работе).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список  источников

1. Новиков Ф.А. Дискретная математика для программистов. — СПб: Питер, 2000. — 304 с.
2. Долинский М. С. Решение сложных и олимпиадных задач по программированию: Учебное пособие. — СПб.: Питер, 2006. — 366 с.
3. Википедия – Свободная Энциклопедия (http://ru.wikipedia.org).
4. Сайт http://urban-sanjoo.narod.ru.
5. Сайт http://e-maxx.ru