Определение кратчайшего расстояния

Федеральное агентство по образованию Федеральное государственное автономное образовательное учреждение высшего профессионального  образования «СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» Институт космических информационных технологий институт Информационные системы кафедра       ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №4   Определение кратчайшего расстояния тема 13 вариант          Студент,     КИ 10-08        _____________                                        номер группы                подпись, дата                              инициалы, фамилия             Преподаватель                   _____________              Л. С. Троценко                                                                                  подпись, дата                       инициалы, фамилия           Красноярск 2013

Содержание

 

 

1 Цель работы

 

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

 

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

 

Для достижения поставленной цели необходимо следовать порядку выполнения.

 

3 Порядок выполнения

 

1. Построить матрицу весов;
2. Для заданной начальной вершины найти кратчайшие расстояния до других вершин графа;
3. Определить кратчайшее расстояние до заданной конечной вершины;
4. Определить кратчайший путь между заданными вершинами.

 

4 Исходные  данные

 

                      74                             60   

 33           44                 32          57

95                                68                              81    

122             44             69             81

   71                              108

 

Рис. 1 Граф

 

 

5 Реализация

 

Вставка из MathCad:

1. Строим матрицу весов:

 

 

 

 

 

 

 

 

Начальная вершина 3

Конечная вершина 7

 

2. определяем расстояния от вершины 3 до всех остальных вершин:

 

Ближайшая к вершине 3 вершина 5, находим  расстояния от вершины 3, через вершину 5 до всех остальных вершин:

 

 

 

 

 

 

 

 

 

 

 

Корректируем расстояния от вершины 3 до остальных вершин:

 

 

Находим расстояния от вершины 3, через вершину 2 до всех остальных вершин:

 

 

 

 

 

 

 

 

 

 

Корректируем расстояния от вершины 3 до остальных вершин:

 

Находим расстояния от вершины 3, через вершину 8 до всех остальных вершин:

 

 

 

 

 

 

 

 

 

 

Корректируем расстояния от вершины 3 до остальных вершин:

 

 

 

 

Находим расстояния от вершины 3, через вершину 4 до всех остальных вершин:

 

 

 

 

 

 

 

 

 

 

Корректируем расстояния от вершины 3 до остальных вершин:

 

 

3. Найдены кратчайшие расстояния  до всех вершин графа от  вершины 3.

Путь до вершины 7: 3-5-7

Длина кратчайшего пути от вершины 3 до вершины 7 равна 126.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

1. Информационные системы логистики [Электронный ресурс] : учеб.-метод. пособие [для студентов спец. 230201.65 «Информационные системы и технологии», бакалавров напр. 230200.62 «Информационные системы» и 230400.62 «Информационные системы и технологии»] / Сиб. федерал. ун-т ; сост. Л. С. Троценко. - Электрон. текстовые дан. (PDF, 628 Кб). - Красноярск : СФУ, 2012. - 50 с.
2. Модели и методы поддержки принятия решений / О. В. Есиков [и др.] ; ред. Е. М. Сухарев. - М. : Радиотехника, 2010. - 191 с. - ISBN 978-5-88070-249-7 
3. Васин, Александр Алексеевич. Исследование операций: учеб. пособие для студентов вузов / А. А. Васин, П. С. Краснощеков, В. В. Морозов. - М. : Академия, 2008. - 464 с. -  ISBN 978-5-7695-4190-2