Инд работа5(нагруженные графы)

Индивидуальная работа №5.

Нагруженные графы. Нахождение кратчайшего пути в нагруженном орграфе. Алгоритм Форда-Беллмана.

Для выполнения и защиты индивидуальной работы №5 необходимо изучить теоретический материал по данной теме.

Перечень основных вопросов по пятой индивидуальной работе:

1. Определения нагруженного графа, длины ребра (дуги), длины маршрута (пути), матрицы длин ребер (дуг) нагруженного графа.

2. Определения расстояния в нагруженном графе, матрицы расстояний, диаметра, радиуса, центра нагруженного графа.

3. Определение кратчайшего маршрута (пути) в нагруженном графе (орграфе). Алгоритм нахождения кратчайшего пути в нагруженном орграфе (алгоритм Форда-Беллмана, алгоритм Дейкстры).

№1. Дан граф:

I II III IV V

VI VII VIII IX X

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

№2. Определить минимальный путь из вершины V₁ в вершину V₇ в нагруженном орграфе с заданной матрицей длин дуг. Построить граф.

I. II. III.

IV. V. VI

VII VIII IX

X

№3. Определить путь из вершины V₁ в вершину V₇ минимальной длины в нагруженном орграфе (см. №2) среди всех путей из V₁ в V₇, содержащих не более К дуг.

а) К=2

б) К=3

в) К=4

№4. С помощью алгоритма Дейкстры определить минимальные пути из V₁ во все остальные в нагруженном орграфе из №2.