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

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

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

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

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

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

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

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