Инд работа5(нагруженные графы)
.docИндивидуальная работа №5.
Нагруженные графы. Нахождение кратчайшего пути в нагруженном орграфе. Алгоритм Форда-Беллмана.
Для выполнения и защиты индивидуальной работы №5 необходимо изучить теоретический материал по данной теме.
Перечень основных вопросов по пятой индивидуальной работе:
-
Определения нагруженного графа, длины ребра (дуги), длины маршрута (пути), матрицы длин ребер (дуг) нагруженного графа.
-
Определения расстояния в нагруженном графе, матрицы расстояний, диаметра, радиуса, центра нагруженного графа.
-
Определение кратчайшего маршрута (пути) в нагруженном графе (орграфе). Алгоритм нахождения кратчайшего пути в нагруженном орграфе (алгоритм Форда-Беллмана, алгоритм Дейкстры).
№1. Дан граф:
I II III IV V
VI VII VIII IX X
Задать длины ребер нагруженного графа. Определить матрицу длин ребер графа. Найти взвешенные эксцентриситет, радиус, диаметр и центр графа.
№2. Определить минимальный путь из вершины V1 в вершину V7 в нагруженном орграфе с заданной матрицей длин дуг. Построить граф.
I. II. III.
IV. V. VI
VII VIII IX
X
№3. Определить путь из вершины V1 в вершину V7 минимальной длины в нагруженном орграфе (см. №2) среди всех путей из V1 в V7, содержащих не более К дуг.
а) К=2
б) К=3
в) К=4
№4. С помощью алгоритма Дейкстры определить минимальные пути из V1 во все остальные в нагруженном орграфе из №2.