Поиск кротчайших путей по алгоритму Флойда

По теме: “Поиск кротчайших путей по алгоритму Флойда” Выполнил: Студент группы ИН-044 Саунин А.В. Руководитель: доцент Белецкая С.Ю. Воронеж 2007 Содержание Введение 1. Сведения о графах 2. Внутреннее представление графов 3. Основные понятия 4. Алгоритм Флойда 5. Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех

пар вершин 6. Задача Флойда 7. Описание программы Поиск кратчайших путей. 8. Листинг программы Заключение Список литературы Введение Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается. Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (напр. кратчайший

путь от дома до академии),также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и мн. др. 1. Сведения о графах В теории графов существуют специфические методы решения экстре¬мальных задач. Один из них основан на теореме о мак¬симальном потоке и минимальном разрезе, утверждаю¬щей, что максимальный поток, который можно пропустить через сеть из вершины

U в вершину V, равен минималь¬ной пропускной способности разрезов, разделяющих вершины U и V. Были построены различные эффективные алгоритмы нахождения макси¬мального потока. Большое значение в теории графов имеют алгоритмические вопросы. Для конечных графов, т. е. для графов с конеч¬ным множеством вершин и ребер, как правило, пробле¬ма существования алгоритма решения задач, в том числе экстремальных, решается положительно.

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

изоморфизма деревьев, нахождения максимального потока. Результаты и методы теории графов применяются при реше¬нии транспортных задач о перевозках, для нахож¬дения оптимальных решений задачи о назначениях, для выделения «узких мест» при планировании и управ¬лении разработок проектов, при составлении оптимальных маршрутов доставки грузов, а также при моделировании сложных технология, процессов, в пост¬роении различных дискретных устройств, в програм¬мировании и т.

д. Граф G (рис.1) задается множеством точек (вершин) х1, х2 хn. (которое обозначается через Х) и множеством линий (ребер) а1, а2 аm. (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (Х, А). Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами,

и граф с такими ребрами называется ориентированным графом, (рис.2).