§11.1. Моделирование на графах | Алгоритмы нахождения кратчайших путей между вершинами графа (11 кл. ФГОС)

Планирование уроков на учебный год (ФГОС)


Урок 17
§11.1. Моделирование на графах



Содержание урока:

11.1. Алгоритмы нахождения кратчайших путей между вершинами графа
11.1. Алгоритмы нахождения кратчайших путей между вершинами графа (Алгоритм построения дерева решений)
11.1. Алгоритмы нахождения кратчайших путей между вершинами графа (Алгоритм Дейкстры)
11.1. Алгоритмы нахождения кратчайших путей между вершинами графа (Метод динамического программирования)
САМОЕ ГЛАВНОЕ. Вопросы и задания
Материалы к уроку


liniya

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


Графы как информационные модели находят широкое применение во многих сферах нашей жизни. Например, с их помощью можно планировать оптимальные транспортные маршруты, кратчайшие объездные пути, расположение торговых точек и других объектов. Необходимость решения задач, связанных с поиском кратчайшего пути на графе, возникает при проектировании инженерных сетей и линий электропередач, в микроэлектронике и во многих других случаях.

Путь между вершинами А и В графа считается кратчайшим, если:

• эти вершины соединены минимальным числом ребер (в случае, если граф не является взвешенным);
• сумма весов рёбер, соединяющих эти вершины, минимальна (для взвешенного графа).

Есть множество алгоритмов определения кратчайшего пути между вершинами графа, в том числе:

1) алгоритм построения дерева решений;
2) алгоритм Дейкстры;
3) метод динамического программирования.

Cкачать материалы урока






Наверх