ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №10. «Нахождение кратчайших путей в графе. Алгоритм Дейкстры»

Стр 1 из 2Следующая ⇒

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №10. «Нахождение кратчайших путей в графе. Алгоритм Дейкстры»

Цель работы:

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

Порядок выполнения работы:

1. Изучить теоретический материал по теме лабораторной работы (лекции, учебники);

2. Согласно номеру своего варианта выбрать условие задачи.

3. Построить взвешенный ориентированный граф согласно условию варианта задачи.

4. Найти с помощью алгоритма Дейкстры кратчайшие расстояния от вершины-источника до всех других вершин графа.

5. Для каждой вершины графа определить вершину предшественника.

6. Оформить отчет по лабораторной работе;

7. Защитить лабораторную работу.

Правила оформления работы

Отчет по лабораторной работе должен содержать:

1) тему работы;

2) ФИО ученика, выполнившего работу;

3) цель работы;

4) формулировку задания согласно номеру варианта;

5) изображение взвешенного ориентированного графа с указанием весов;

6) описание метода нарождения кратчайших путей в графе согласно алгоритму;

7) решение задания с помощью алгоритма Дейкстры (должно содержать таблицу расстояний D и вектор вершин-предшественников).

УСЛОВИЕ ЗАДАЧИ

Дан взвешенный ориентированный граф с 10 вершинами.

Найти с помощью алгоритма Дейкстры кратчайшие пути в графе от источника I – вершины 1, до всех других вершин графа. Направление ориентации дуг графа определяется порядком следования индексов весов на графе. Значение индекса указывает номер начальной вершины дуги, значение индекса – конечной вершины.

12 Следующая ⇒