Исследование алгоритма Флойда для маршрутизации пакетов в компьютерной сети

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Исследование алгоритма Флойда для маршрутизации пакетов в компьютерной сети



Введение

программирование маршрутизация флойд алгоритм

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

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

Вычислительные сети представляют собой систему компьютеров, объединенных линиями связи и специальными устройствами, позволяющими передавать без искажения и переключать между компьютерами потоки данных.

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

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

Цель курсового проекта состоит в анализе целей и задач маршрутизации в вычислительных сетях с пакетной обработкой информации. Провести исследование существующих алгоритмов маршрутизации (в частности алгоритма Флойда), применяемых в корпоративных вычислительных сетях, чтобы выявить достоинства, недостатки и область их применения.

В процессе предварительного изучения проблемы было решено начать с анализа основных алгоритмов маршрутизации сетевого трафика. Основная работа маршрутизатора на сетевом уровне заключается в маршрутизации пакетов, т.е. в передаче данных с входных портов на выходные с учетом адресной информации (IP-адресов), заложенной в пакетах. Для осуществления указанной функции маршрутизатор оперирует таблицей маршрутизации, которую формирует сам с использованием одного из алгоритмов построения дерева кратчайших путей. На практике обычно используются два основных алгоритма маршрутизации - Дейкстры и Флойда, применяемые в протоколах маршрутизации OSPF и RIP соответственно.



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

1.1 Цель и задачи

Основной целью данной работы анализ целей и задач маршрутизации в вычислительных сетях с пакетной обработкой информации.

Задача, которую необходимо реализовать в данном курсовом проекте заключается в следующем: выбрать три схемы из лабораторной работы №7 по желанию.

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

Найти (в каждой из трех схем):

- узел, с которого можно передать сигналы остальным с наименьшими затратами;

- номер этого узла;

- массив путей обхода маршрутов для произвольных узлов сети. [2]

1.2 Обоснование выбора средства программирования

Программа разрабатывалась при помощи Microsoft Visual Studio 2012 на языке C#. Данная среда выгодно отличается эффективностью и надежностью. К тому же С# - признанный стандарт во всём мире.

1.3 Входная информация

Входными данными для программы являются матрицы смежности, заполненные с помощью элемента управления dataGridView.



1.4 Выходная информация

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

1.5 Требования к аппаратному обеспечению

Для стабильного функционирования программы необходим компьютер фирмы IBM или совместимый с ним, с объёмом оперативной памяти не менее 4 Мб.

1.6 Требования к программному обеспечению

Для функционирования данного программного продукта на компьютере должна быть установлена операционная система WINDOWS 7, или более поздняя версия.



2. Теоретическая часть

2.1 Алгоритм маршрутизации Флойда

Задача маршрутизации состоит в выборе маршрута для передачи от отправителя к получателю. Она имеет смысл в сетях, где не только необходим, но и возможен выбор оптимального или приемлемого маршрута. Речь идет, прежде всего, о сетях с произвольной (ячеистой) топологией, в которых реализуется коммутация пакетов. Однако в современных сетях со смешанной топологией (звездио-кольцевой, звездио-шиниой, многосегментиой) реально стоит и решается задача выбора маршрута для передачи кадров, для чего используются соответствующие средства, например маршрутизаторы.

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

Выбор маршрутов в узлах связи ТКС производится в соответствии с реализуемым алгоритмом (методом) маршрутизации.

Алгоритм маршрутизации - это правило назначения выходной линии связи данного узла связи ТКС для передачи пакета, базирующееся на информации, содержащейся в заголовке пакета (адреса отправителя и получателя), и информации о загрузке этого узла (длина очередей пакетов) и, возможно, ТКС в целом

Основные цели маршрутизации заключаются в обеспечении:

- минимальной задержки пакета при его передаче от отправителя к получателю;

- максимальной пропускной способности сети, что достигается, в частности, нивелировкой загрузки линий связи ТКС;

- максимальной защиты пакета от угроз безопасности содержащейся в нем информации;

- надежности доставки пакета адресату;

- минимальной стоимости передачи пакета адресату.

Различают следующие способы маршрутизации.

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

2. Распределенная (децентрализованная) маршрутизация выполняется главным образом в сетях с децентрализованным управлением. Функции управления маршрутизацией распределены между узлами сети, которые располагают для этого соответствующими средствами. Распределенная маршрутизация сложнее централизованной, но отличается большей гибкостью.

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

Задача маршрутизации в сетях решается при условии, что кратчайший маршрут, обеспечивающий передачу пакета за минимальное время, зависит от топологии сети, пропускной способности линий связи, нагрузки на линии связи. Топология сети изменяется в результате отказов узлов и линий связи и отчасти при развитии ТКС (подключении новых узлов и линий связи). Пропускная способность линий связи определяется типом передающей среды и зависит от уровня шумов и параметров аппаратуры, обслуживающей линии. Наиболее динамичным фактором является нагрузка на линии связи, изменяющаяся довольно быстро и в трудно прогнозируемом направлении.

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

Эффективность алгоритмов маршрутизации оценивается следующими показателями:

- временем доставки пакетов адресату;

- нагрузкой на сеть, которая при реализации данного алгоритма создается потоками пакетов, распределяемыми по линиям и узлам сети.

Количественная оценка нагрузки осуществляется длиной очередей пакетов в узлах;

- затратами ресурсов в узлах связи (временем работы коммуникационной ЭВМ, емкостью памяти).

Факторы, снижающие эффективность алгоритмов маршрутизации:

- передача пакета в узел связи, находящийся под высокой нагрузкой;

- передача пакета в направлении, не приводящем к минимальному времени его доставки;

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

Методы маршрутизации. Различают три вида маршрутизации - простую, фиксированную и адаптивную. Принципиальная разница между ними - в степени учета изменения топологии и нагрузки сети при решении задачи выбора маршрута. [3]



2.2 Поиск кратчайшего пути

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

Для объединенной сети, такой как Интернет или интранет, представление ее в виде ориентированного графа также является приемлемым. В этом случае каждой вершине соответствует маршрутизатор. Если два маршрутизатора напрямую присоединены к одной и той же локальной или глобальной сети, тогда это двустороннее соединение соответствует паре параллельных ребер, соединяющих соответствующие вершины. Если к сети напрямую присоединены более двух маршрутизаторов, тогда эта сеть представляется в виде множества пар параллельных ребер, каждая из которых соединяет два маршрутизатора. В объединенной сети для передачи IP-дейтаграммы от маршрутизатора-источника к маршрутизатору-приемнику по разным линиям через разные сети и маршрутизаторы пакетов, требуется принять решение о выборе маршрута. Эта задача также эквивалентна поиску пути в графе.

Практически во всех сетях с коммутацией пакетов и во всех объединенных сетях решение о выборе маршрута принимается на основе одной из разновидностей критерия минимальной стоимости. Если выбирается маршрут с минимальным количеством ретрансляционных участков (хопов), тогда каждому ребру, соответствующему ретрансляционному участку, назначается единичный вес. Эта задача соответствует поиску кратчайшего пути в обычном (не взвешенном) графе. Но чаще всего каждому ретрансляционному участку в соответствие ставится определенная величина, называемая стоимостью (cost) передачи. Эта величина может быть обратно пропорциональной пропускной способности линии, прямо пропорциональной текущей нагрузке на эту линию или представлять собой некую комбинацию подобных параметров. При расчете стоимости могут учитываться также такие критерии, как финансовая стоимость использования ретрансляционного участка.

Пусть имеется сеть, состоящая из узлов, соединенных двунаправленными линиями связи, и каждой линии поставлена в соответствие стоимость пересылки данных в каждом направлении. Стоимость пути между двумя узлами определяется как сумма стоимость всех линий, входящих в данный путь. Задача состоит в том, чтобы найти путь с наименьшей стоимостью для каждой пары узлов.

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

Большинство алгоритмов поиска маршрута с наименьшей стоимостью, применяются в сетях с коммутацией пакетов и объединенных сетях, представляют собой вариации одного из двух общих алгоритмов, известных как алгоритм Дейкстры и алгоритм Флойда. [4]



3. Алгоритм решения задачи

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

3.1 Алгоритм Флойда

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

1. Разбиение задачи на подзадачи меньшего размера;

2. Нахождение оптимального решения подзадач рекурсивно;

3. Использование полученного решения подзадач для конструирования решения исходной задачи.

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

Мы используем представление графа в виде матрицы смежностей.

for k:=1 to n do begin

for i:=1 to n do begin

for j:=1 to n do begin

if (mas[i, j]<=(mas [i, k]+mas [k, j])) then mas [i, j]:=mas [i, j]

else mas [i, j]:=mas [i, k]+mas [k, j];

end;

end;

end;

где mas [i, j] - сначала длина дуги, а в конце - длина кратчайшего пути.

Как видно алгоритм очень прост - сначала происходит инициализация матрицы кратчайших расстояний D0, изначально она совпадает с матрицей смежности, в цикле увеличиваем значение k и пересчитываем матрицу расстояний, из D0 получаем D1, из D1 - D2 и так далее до k=n.

Предполагается, что если между двумя какими-то вершинами нет ребра, то в матрице смежности было записано какое-то большое число (достаточно большое, чтобы оно было больше длины любого пути в этом графе), тогда это ребро всегда будет невыгодно брать, и алгоритм сработает правильно. Правда, если не принять специальных мер, то при наличии в графе рёбер отрицательного веса, в результирующей матрице могут появиться числа вида ?-1, ?-2, и т.д., которые, конечно, по-прежнему означают, что между соответствующими вершинами вообще нет пути. Поэтому при наличии в графе отрицательных рёбер алгоритм Флойда лучше написать так, чтобы он не выполнял переходы из тех состояний, в которых уже стоит «нет пути». [5]



4. Описание программы

4.1 Формулировка задачи

Задача, которую необходимо реализовать в данном курсовом проекте заключается в следующем: выбрать три схемы из лабораторной работы №7 по желанию.

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

Найти (в каждой из трех схем):

- узел, с которого можно передать сигналы остальным с наименьшими затратами;

- номер этого узла;

- массив путей обхода маршрутов для произвольных узлов сети. [2]

4.2 Реализация поставленной задачи

Программа разрабатывалась при помощи Microsoft Visual Studio 2010 на языке C#.

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

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

Далее используется алгоритм Флойда-Уоршолла, чтобы вычислить силу каждого из возможных путей. Метод Max в коде работает над обеспечением того, чтобы при каждом проходе через внешний цикл обновлялась матрица результатов, только если найден более сильный путь. Метод Min в коде соответствует идее использования наименьшей силы между узлами для представления общей силы пути, существующей между любыми двумя узлами.

После того, как в наличии имеются все силы путей, можно использовать эту информацию для вычисления одномерного массива, представляющего узлы, с которых можно передать сигналы остальным с наименьшими затратами по методу Шульце. С помощью этого метода устанавливается одномерный логический массив в поле textBox, где значение true указывает победителя, а значение false - все остальных. Предполагается, что каждый из вариантов является тем узлом, который мы ищем, затем матрица силы путей перебирается для сравнения значение силы в индексе [j, i] с тем же в индексе [i, j], чтобы увидеть, является ли этот вариант тем узлом, который нам нужен, на самом деле. [6]

Этот алгоритм в коде реализован для каждой из трех схем отдельно.

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

Блок схемы к каждому этапу решения приведены в приложениях 1 и 2 соответственно. В приложении 3 приведен листинг программы.



4.3 Пользовательский интерфейс программы и совокупность последовательных этапов взаимодействия конечного пользователя с программой

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

Пользовательский интерфейс программы

Приведем пример решения поставленной задачи на схеме 1. Для этого пользователю необходимо выбрать первый вариант, поставив галочку в соответствующем поле. Затем для нахождения узла, с которого можно передать сигналы остальным с наименьшими затратами, пользователю необходимо нажать верхнюю кнопку «пуск», результат этой операции приведен на рисунке.



Пользовательский интерфейс программы

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

Пользовательский интерфейс программы

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



Заключение

Цель курсового проекта состоит в анализе целей и задач маршрутизации в вычислительных сетях с пакетной обработкой информации. Было проведено исследование существующих алгоритмов маршрутизации (в частности алгоритма Флойда), применяемых в корпоративных вычислительных сетях и выявлены достоинства, недостатки и область их применения.

При анализе времени работы и использования памяти алгоритмом Флойда было определено, что алгоритму требуется O(n³) памяти, для сохранения матриц. Однако количество матриц можно легко сократить до двух, каждый раз переписывая ненужную матрицу или вообще перейти к двухмерной матрице, убрав индекс k у d^k_ij. Лучший вариант, который чаще всего используется - писать сразу в матрицу смежности, тогда нам совсем не нужна дополнительная память, правда если сразу переписывать изначальную матрицу, то нужно дополнительно показать корректность алгоритма, так как классическое академическое доказательство верно только для случая, когда матрица предыдущей итерации не изменяется.

Что касается времени работы то оно равно трем вложенным циклам от 1 до n - O(n³) Однако, алгоритм поиска оптимальных маршрутов с учетом частичных изменений структуры сети на основе дополнительной информации о возможных парных переходах позволяет получить меньшую трудоемкость поиска оптимальных маршрутов (O(n), где n - число узлов в сети), по сравнению с алгоритмом Флойда.

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

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

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

Скажем, если вы возьмете карту города - её транспортная система это граф, соответственно присвоив каждому ребру некую стоимость, рассчитанную скажем из пропускной способности и других важный параметров - вы сможете подвести попутчика по самому короткому быстрому дешевому пути. [5]



Список литературы

1. Архитектура компьютерных систем и сетей: Учебное пособие. / Т.П. Барановская, В.И. Лойко, М.И. Семенов, А.И. Трубилин. Под ред. В.И. Лойко. - М: Финансы и статистика, 2003. - 291 с.: ил.

2. Лойко В.И. и др. Вычислительные системы, сети и телекоммуникации: Методические указания по подготовке курсовых работ (для студентов специальностей 351400 - Прикладная информатика в экономике). - Краснодар: КубГТУ, 2003. - 46 с.

3. Вычислительные системы, сети и телекоммуникации; Учебник. - 2-е изд., перераб. и доп. / А.П. Пятибратов, Л.П. Гудыно, A.A. Кириченко; Под ред. А.П. Пятибратова - М.: Финансы и статистика, 2004. - 512 с: ил.

4. Современные компьютерные сети. 2-е изд./В. Столингс. - СПб.: Питер, 2003. - 783 с.

5. habr.ru - сайт прогрессивно мыслящих людей, интересующихся будущим IT-рынка в целом и интернет-экономикой в частности.

6. msdn.microsoft.com/ru-ru/magazine/dd239189.aspx - журнал MSDN Magazine Ноябрь 2008.



Приложение 1

Листинг программы на языке C#

using System;

using System. Collections. Generic;

using System. ComponentModel;

using System. Data;

using System. Drawing;

using System. Linq;

using System. Text;

using System. Windows. Forms;

namespace Флоид

{

public partial class Form1: Form

{

public Form1 ()

{

InitializeComponent();

}

enum options {A, B, C, D, E, F};

static int N = 6;

 // нахождение узла, с которого можно передать сигналы остальным с наименьшими затратами.

private void button1_Click (object sender, EventArgs e)

{

 // для первого варианта

if (checkBox1. Checked == true)

{

dataGridView1. Rows. Clear(); // обновление таблицы

 // заполнение матрицы смежности

dataGridView1. Rows. Add (0, 1, 100, 1, 100, 100);

dataGridView1. Rows[0].HeaderCell. Value = «A»;

dataGridView1. Rows. Add (1, 0, 3, 2, 3, 3);

dataGridView1. Rows[1].HeaderCell. Value = «B»;

dataGridView1. Rows. Add (100, 3, 0, 1, 100, 2);

dataGridView1. Rows[2].HeaderCell. Value = «C»;

dataGridView1. Rows. Add (1, 2, 1, 0, 2, 100);

dataGridView1. Rows[3].HeaderCell. Value = «D»;

dataGridView1. Rows. Add (100, 3, 100, 2, 0, 3);

dataGridView1. Rows[4].HeaderCell. Value = «E»;

dataGridView1. Rows. Add (100, 3, 2, 100, 3, 0);

dataGridView1. Rows[5].HeaderCell. Value = «F»;

 // алгоритм Флойда

for (int k = 0; k < N; ++k)

{

for (int i = 0; i < N; ++i)

{

if (k == i) continue;

for (int j = 0; j < N; ++j)

{

if (k == j || i == j) continue;

dataGridView1 [j, i].Value = Math. Max((int) dataGridView1 [j, i].Value, Math. Min((int) dataGridView1 [k, i].Value, (int) dataGridView1 [j, k].Value));

} //j

} //i

} //k

 // поиск уела, с которого можно передать сигналы остальным с наименьшими затратами по методу Шульце

bool[] winners = new bool[N];

for (int i = 0; i < N; ++i)

winners[i] = true;

for (int i = 0; i < N; ++i)

{

for (int j = 0; j < N; ++j)

if ((int) dataGridView1 [j, i].Value < (int) dataGridView1 [i, j].Value)

winners[i] = false;

}

for (int i = 0; i < winners. Length; ++i)

if (winners[i] == true)

textBox1. Text = Enum. GetName (typeof(options), i);

dataGridView1. Rows. Clear();

dataGridView1. Rows. Add (0, 1, «X», 1, «X», «X»);

dataGridView1. Rows[0].HeaderCell. Value = «A»;

dataGridView1. Rows. Add (1, 0, 3, 2, 3, 3);

dataGridView1. Rows[1].HeaderCell. Value = «B»;

dataGridView1. Rows. Add («X», 3, 0, 1, «X», 2);

dataGridView1. Rows[2].HeaderCell. Value = «C»;

dataGridView1. Rows. Add (1, 2, 1, 0, 2, «X»);

dataGridView1. Rows[3].HeaderCell. Value = «D»;

dataGridView1. Rows. Add («X», 3, «X», 2, 0, 3);

dataGridView1. Rows[4].HeaderCell. Value = «E»;

dataGridView1. Rows. Add («X», 3, 2, «X», 3, 0);

dataGridView1. Rows[5].HeaderCell. Value = «F»;

}

 // для второго варианта

if (checkBox2. Checked == true)

{

dataGridView1. Rows. Clear(); // обновление таблицы

dataGridView1. Rows. Add (0, 1, 100, 2, 3, 3);

dataGridView1. Rows[0].HeaderCell. Value = «A»;

dataGridView1. Rows. Add (1, 0, 100, 100, 1, 2);

dataGridView1. Rows[1].HeaderCell. Value = «B»;

dataGridView1. Rows. Add (100, 100, 0, 2, 100, 3);

dataGridView1. Rows[2].HeaderCell. Value = «C»;

dataGridView1. Rows. Add (2, 100, 2, 0, 100, 100);

dataGridView1. Rows[3].HeaderCell. Value = «D»;

dataGridView1. Rows. Add (3, 1, 100, 100, 0, 3);

dataGridView1. Rows[4].HeaderCell. Value = «E»;

dataGridView1. Rows. Add (3, 2, 3, 100, 3, 0);

dataGridView1. Rows[5].HeaderCell. Value = «F»;

for (int k = 0; k < N; ++k)

{

for (int i = 0; i < N; ++i)

{

if (k == i) continue;

for (int j = 0; j < N; ++j)

{

if (k == j || i == j) continue;

dataGridView1 [j, i].Value = Math. Max((int) dataGridView1 [j, i].Value, Math. Min((int) dataGridView1 [k, i].Value, (int) dataGridView1 [j, k].Value));

} //j

} //i

} //k

bool[] winners = new bool[N];

for (int i = 0; i < N; ++i)

winners[i] = true;

for (int i = 0; i < N; ++i)

{

for (int j = 0; j < N; ++j)

if ((int) dataGridView1 [j, i].Value < (int) dataGridView1 [i, j].Value)

winners[i] = false;

}

for (int i = 0; i < winners. Length; ++i)

if (winners[i] == true)

textBox1. Text = Enum. GetName (typeof(options), i);

dataGridView1. Rows. Clear();

dataGridView1. Rows. Add (0, 1, «X», 2, 3, 3);

dataGridView1. Rows[0].HeaderCell. Value = «A»;

dataGridView1. Rows. Add (1, 0, «X», «X», 1, 2);

dataGridView1. Rows[1].HeaderCell. Value = «B»;

dataGridView1. Rows. Add («X», «X», 0, 2, «X», 3);

dataGridView1. Rows[2].HeaderCell. Value = «C»;

dataGridView1. Rows. Add (2, «X», 2, 0, «X», «X»);

dataGridView1. Rows[3].HeaderCell. Value = «D»;

dataGridView1. Rows. Add (3, 1, «X», «X», 0, 3);

dataGridView1. Rows[4].HeaderCell. Value = «E»;

dataGridView1. Rows. Add (3, 2, 3, «X», 3, 0);

dataGridView1. Rows[5].HeaderCell. Value = «F»;

}

 // для третьего варианта

if (checkBox3. Checked == true)

{

dataGridView1. Rows. Clear(); // обновление таблицы

dataGridView1. Rows. Add (0, 1, 5, 2, 100, 100);

dataGridView1. Rows[0].HeaderCell. Value = «A»;

dataGridView1. Rows. Add (1, 0, 100, 1, 3, 100);

dataGridView1. Rows[1].HeaderCell. Value = «B»;

dataGridView1. Rows. Add (5, 100, 0, 4, 2, 3);

dataGridView1. Rows[2].HeaderCell. Value = «C»;

dataGridView1. Rows. Add (2, 1, 4, 0, 100, 4);

dataGridView1. Rows[3].HeaderCell. Value = «D»;

dataGridView1. Rows. Add (100, 3, 2, 2, 0, 1);

dataGridView1. Rows[4].HeaderCell. Value = «E»;

dataGridView1. Rows. Add (100, 100, 3, 4, 1, 0);

dataGridView1. Rows[5].HeaderCell. Value = «F»;

for (int k = 0; k < N; ++k)

{

for (int i = 0; i < N; ++i)

{

if (k == i) continue;

for (int j = 0; j < N; ++j)

{

if (k == j || i == j) continue;

dataGridView1 [j, i].Value = Math. Max((int) dataGridView1 [j, i].Value, Math. Min((int) dataGridView1 [k, i].Value, (int) dataGridView1 [j, k].Value));

} //j

} //i

} //k

bool[] winners = new bool[N];

for (int i = 0; i < N; ++i)

winners[i] = true;

for (int i = 0; i < N; ++i)

{

for (int j = 0; j < N; ++j)

if ((int) dataGridView1 [j, i].Value < (int) dataGridView1 [i, j].Value)

winners[i] = false;

}

for (int i = 0; i < winners. Length; ++i)

if (winners[i] == true)

textBox1. Text = Enum. GetName (typeof(options), i);



dataGridView1. Rows. Clear();

dataGridView1. Rows. Add (0, 1, 5, 2, «X», «X»);

dataGridView1. Rows[0].HeaderCell. Value = «A»;

dataGridView1. Rows. Add (1, 0, «X», 1, 3, «X»);

dataGridView1. Rows[1].HeaderCell. Value = «B»;

dataGridView1. Rows. Add (5, «X», 0, 4, 2, 3);

dataGridView1. Rows[2].HeaderCell. Value = «C»;

dataGridView1. Rows. Add (2, 1, 4, 0, «X», 4);

dataGridView1. Rows[3].HeaderCell. Value = «D»;

dataGridView1. Rows. Add («X», 3, 2, 2, 0, 1);

dataGridView1. Rows[4].HeaderCell. Value = «E»;

dataGridView1. Rows. Add («X», «X», 3, 4, 1, 0);

dataGridView1. Rows[5].HeaderCell. Value = «F»;

}

}

 // построение массива кратчайших путей

private void button2_Click (object sender, EventArgs e)

{

 // для первого варианта

if (checkBox1. Checked == true)

{

dataGridView2. Rows. Clear(); // обновление таблицы

dataGridView2. Rows. Add (0, 1, 100, 1, 100, 100);

dataGridView2. Rows[0].HeaderCell. Value = «A»;

dataGridView2. Rows. Add (1, 0, 3, 2, 3, 3);

dataGridView2. Rows[1].HeaderCell. Value = «B»;

dataGridView2. Rows. Add (100, 3, 0, 1, 100, 2);

dataGridView2. Rows[2].HeaderCell. Value = «C»;

dataGridView2. Rows. Add (1, 2, 1, 0, 2, 100);

dataGridView2. Rows[3].HeaderCell. Value = «D»;

dataGridView2. Rows. Add (100, 3, 100, 2, 0, 3);

dataGridView2. Rows[4].HeaderCell. Value = «E»;

dataGridView2. Rows. Add (100, 3, 2, 100, 3, 0);

dataGridView2. Rows[5].HeaderCell. Value = «F»;

 // алгоритм Флойда

for (int k = 0; k < N; ++k)

for (int i = 0; i < N; ++i)

for (int j = 0; j < N; ++j)

if ((int) dataGridView2 [j, k].Value!= int. MaxValue && (int) dataGridView2 [k, i].Value!= int. MaxValue)

{

int d = (int) dataGridView2 [j, k].Value + (int) dataGridView2 [k, i].Value;

if ((int) dataGridView2 [j, i].Value > d)

dataGridView2 [j, i].Value = d;

}

}

 // для второго варианта

if (checkBox2. Checked == true)

{

dataGridView2. Rows. Clear(); // обновление таблицы

dataGridView2. Rows. Add (0, 1, 100, 2, 3, 3);

dataGridView2. Rows[0].HeaderCell. Value = «A»;

dataGridView2. Rows. Add (1, 0, 100, 100, 1, 2);

dataGridView2. Rows[1].HeaderCell. Value = «B»;

dataGridView2. Rows. Add (100, 100, 0, 2, 100, 3);

dataGridView2. Rows[2].HeaderCell. Value = «C»;

dataGridView2. Rows. Add (2, 100, 2, 0, 100, 100);

dataGridView2. Rows[3].HeaderCell. Value = «D»;

dataGridView2. Rows. Add (3, 1, 100, 100, 0, 3);

dataGridView2. Rows[4].HeaderCell. Value = «E»;

dataGridView2. Rows. Add (3, 2, 3, 100, 3, 0);

dataGridView2. Rows[5].HeaderCell. Value = «F»;

for (int k = 0; k < N; ++k)

for (int i = 0; i < N; ++i)

for (int j = 0; j < N; ++j)

if ((int) dataGridView2 [j, k].Value!= int. MaxValue && (int) dataGridView2 [k, i].Value!= int. MaxValue)

{

int d = (int) dataGridView2 [j, k].Value + (int) dataGridView2 [k, i].Value;

if ((int) dataGridView2 [j, i].Value > d)

dataGridView2 [j, i].Value = d;

}

}

 // для третьего варианта

if (checkBox3. Checked == true)

{

dataGridView2. Rows. Clear(); // обновление таблицы

dataGridView2. Rows. Add (0, 1, 5, 2, 100, 100);

dataGridView2. Rows[0].HeaderCell. Value = «A»;

dataGridView2. Rows. Add (1, 0, 100, 1, 3, 100);

dataGridView2. Rows[1].HeaderCell. Value = «B»;

dataGridView2. Rows. Add (5, 100, 0, 4, 2, 3);

dataGridView2. Rows[2].HeaderCell. Value = «C»;

dataGridView2. Rows. Add (2, 1, 4, 0, 100, 4);

dataGridView2. Rows[3].HeaderCell. Value = «D»;

dataGridView2. Rows. Add (100, 3, 2, 2, 0, 1);

dataGridView2. Rows[4].HeaderCell. Value = «E»;

dataGridView2. Rows. Add (100, 100, 3, 4, 1, 0);

dataGridView2. Rows[5].HeaderCell. Value = «F»;

for (int k = 0; k < N; ++k)

for (int i = 0; i < N; ++i)

for (int j = 0; j < N; ++j)

if ((int) dataGridView2 [j, k].Value!= int. MaxValue && (int) dataGridView2 [k, i].Value!= int. MaxValue)

{

int d = (int) dataGridView2 [j, k].Value + (int) dataGridView2 [k, i].Value;

if ((int) dataGridView2 [j, i].Value > d)

dataGridView2 [j, i].Value = d;

}

}

}

}

}

Размещено на Allbest.ru