Реализация алгоритма Беллмана-Форда поиска кратчайших путей от заданной вершины

Реферат

Отчет 11 с., 2 рис., 1 табл., 3 источ., 1 прил.

ГРАФЫ, АЛГОРИТМ, ПРОГРАММА, КРАТЧАЙШИЙ ПУТЬ, ВЫЧИСЛЕНИЕ

Объектом исследования является ориентированный граф с взвешенными рёбрами.

Цель работы – реализация алгоритма Беллмана-Форда, посредством языка программирования C#.

В процессе работы проводилось тщательное изучение алгоритма Форда-Беллмана и некоторых основ языка C#.

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

Основные конструктивные и технико-эксплуатационные показатели: простота в использовании и доступность для любого уровня пользователей.

Степень внедрения – для учебных целей.

Эффективность программы определяется в простоте алгоритма и способностью быть наглядным примером для представления ориентированных графов.

Содержание

Введение        6

1 Постановка задачи        7

2 Схема основных алгоритмов        7

3 Аспекты реализации на языке C#        8

4 Руководство пользователя        8

5 Результаты тестирования        8

Заключение        9

Список использованных источников        10

Приложение А        11

Введение

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

Именно для таких целей был разработан язык C#, способный воплотить в программе любые решения разработчика, чтобы улучшить производительность труда или же просто сделать простой расчет гораздо легче обычного.

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

1 Постановка задачи

Задача – реализовать алгоритм Беллмана-Форда поиска кратчайших путей от заданной вершины.

2 Схема основных алгоритмов

Пусть V – количество вершин в графе, S – начальная вершина, d – массив расстояний, A – массив весов рёбер.

Тогда схема алгоритмов имеет вид, представленный на рисунке 1.

[pic 1][pic 2][pic 3][pic 4]

[pic 5][pic 6][pic 7][pic 8][pic 9][pic 10][pic 11][pic 12][pic 13][pic 14][pic 15][pic 16][pic 17][pic 18][pic 19][pic 20][pic 21][pic 22][pic 23][pic 24][pic 25][pic 26][pic 27][pic 28][pic 29][pic 30][pic 31][pic 32][pic 33][pic 34][pic 35][pic 36][pic 37][pic 38][pic 39][pic 40][pic 41][pic 42][pic 43][pic 44][pic 45][pic 46][pic 47][pic 48][pic 49][pic 50][pic 51][pic 52][pic 53][pic 54][pic 55][pic 56][pic 57][pic 58][pic 59][pic 60][pic 61][pic 62][pic 63][pic 64][pic 65][pic 66][pic 67]

Рисунок 1 – Схема алгоритмов

3 Аспекты реализации на языке C#

В процессе реализации алгоритма было использовано следующее: функция случайного заполнения матрицы смежности в определенном диапазоне, оператор «try-catсh», а также алгоритм Беллмана-Форда [1].

4 Руководство пользователя

Программа разработана на Windows Form Application, что, несомненно, улучшает интерфейс и позволяет работать пользователям любого уровня [2]. Для того, чтобы вычислить кратчайший путь от какой-либо вершины, достаточно задать матрицу смежности и нажать кнопку «Вычислить». После чего программа выдаст результат, представленный в виде последовательности чисел.