Лабораторная работа 1 1 Свойства графов. Поиск кратчайших путей в графе по дисциплине Моделирование инфокоммуникационных систем
 Скачать 1.16 Mb.
|
|
Министерство науки и высшего образования Российской Федерации федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет ИТМО» Факультет инфокоммуникационных технологий Лабораторная работа №1_1 «Свойства графов. Поиск кратчайших путей в графе» по дисциплине: «Моделирование инфокоммуникационных систем» Выполнил: студент(ка) I курса ИКТ группы К3140 Ф.И.О. Чуб Илья Евгеньевич Проверил: доцент ФИКТ Валитова Юлия Олеговна Санкт-Петербург 2021 Цель лабораторной работы: освоить способ нахождения кратчайшего пути в графе с использованием средства Microsoft Excel. Ход выполнения работы. С целью закрепления своих знаний в программировании на языке Python, для нахождения кратчайшего пути в графе были использованы не только средства Microsoft Excel, но и средства Python. Для этого в рабочее окружение было необходимо добавить три модуля, не встроенных по умолчанию в Python: - openpyxl – для чтения excel файла и записи в него; - networkx – для составления графа; - mathplotlib – для отрисовки графа. После того, как модули были добавлены в рабочее окружение и был прописан их импорт в коде (название фала с кодом – logic.py), можно было приступать к написанию функций. Первую функцию, которую было необходимо написать – это функцию чтения excel файла с последующим составлением массива вершин и словаря, ключ которого – город, а значение – координаты этого города (Рисунок 1 – Функция "defining_graph_vertices", см. Приложение А). Далее была написана функция для чтения excel файла и составление матрицы будущего графа в виде двумерного массива (Рисунок 2 – Функция "defining_graph_edges", см. Приложение А). И последняя функция, которая была написана – функция, основанная на алгоритме Дейкстры, находящая кратчайшие расстояния из начального города во все остальные (в виде массива), а также готовый путь из начального города в конечный (в виде массива) (Рисунок 3 – Функция "Dijkstra", см. Приложение А). В последующей части кода идёт использование этих функция и их результатов, отрисовка графа и вывод данных. Так как excel файл похож по структуре на zip файл, то мгновенное отображение (без переоткрытия) только что записанных извне excel данных практически невозможно, то было решено результаты работы выводить в отдельный excel файл (1_lab_result.xlsx) (Рисунок 4 – Вывод результатов, см. Приложение А), а рисунок графа сохранять в рабочей директории в виде отдельной PNG картинки (1_lab_graph.png) ((Рисунок 5 – Рисунок графа, см. Приложение А)). Выводы по результатам работы В процессе выполнения данной лабораторной работы я узнал: как использовать Python и Microsoft Excel в связке; как составлять и отрисовывать графы с использованием сторонних модулей Python; базовые алгоритмы для нахождения кратчайших путей в графах. Считаю, что полученные навыки и знания помогут мне в дальнейшем освоении как теории графов и Microsoft Excel, так и языка программирования Python. П  РИЛОЖЕНИЕ АРисунок 1 – Функция "defining_graph_vertices "  Рисунок 2 – Функция "defining_graph_edges"   Рисунок 3 – Функция "Dijkstra",  Р  исунок 4 – Вывод результатовРисунок 5 – Рисунок графа |