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

Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе.Цель алгоритма Флойда - определение кратчайшего пути между вершинами взвешенного графа.Задачи нахождения кратчайшего пути.Дан граф смежности для нахождения минимального пути от вершины 1 до всех остальных (рис. 4.1.).Дан граф смежности для нахождения минимального пути от вершины 1 до всех остальных.Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №1 для исходного графа.Таким образом, в этом случае кратчайшего пути не существует.Рис. 4.9 Результат работы алгоритма показан на графе.Рис.4.13. Результат работы алгоритма показан на графе.Стартовая вершина, от которой строится дерево кратчайших путей - вершина 1.