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

Министерство образования и науки РФ 

Федеральное государственное автономное образовательное учреждение высшего образования

 «Омский государственный технический университет»

КУРСОВОЙ ПРОЕКТ

Пояснительная записка

                                        Набранные баллы:   ______   _____   ___________        

        в семестре    на защите     Итого

Омск 2022

РЕФЕРАТ

Пояснительная записка к курсовому проекту 17 с., 1 ч., 8 рис., 2 табл., 1 источ., 2 прил.

АЛГОРИТМ, ФЛОЙД-УОРШЕЛЛ, ГРАФ, МАТРИЦА, КРАТЧАЙШИЕ ПУТИ, ВЕРШИНЫ.

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

Цель работы – реализовать алгоритм Флойда-Уоршелл для построения кратчайших путей между всеми парами вершин графа.

В ходе работы проводилась разработка алгоритма и его реализация на языке программирования высокого уровня С#.

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

СОДЕРЖАНИЕ

Введение        4

1. Постановка задачи курсового проектирования        5
2. Схема основного алгоритма        5
3. Описание структур данных        5
4. Аспекты реализации на языке С#        5
5. Руководство пользователя        7
6. Методика тестирования        8

Заключение        9

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

Приложение А Тестирование        11

Приложение Б Исходный код программы        12

ВВЕДЕНИЕ

Курсовой проект по дисциплине “Программирование”, 1 курс. В проекте использовался язык программирования С#.

Задача: разработать программу, которая будет искать кратчайшие пути между всеми вершинами графа. Программа будет основа на алгоритме Флойда-Уоршелла, этот алгоритм предназначен для поиска кратчайших путей во взвешенном графе с положительным или отрицательным весом ребер (но без отрицательных циклов). За одно выполнение алгоритма будут найдены длины (суммарные веса) кратчайших путей между всеми парами вершин [1]. 

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

1. Постановка задачи курсового проектирования

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

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

Данный раздел содержит схему алгоритма.

На рисунке 2.1 представлена схема алгоритма.

1. Описание структур данных

Описание структур данных приведено в таблице 1. Размеры указаны без учёта памяти, используемой структурами для хранения служебной информации.

Таблица 1 – Описание структур данных