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

Краткая выдержка из текста работы (Аннотация)

Цель работы.

Целью курсовой работы было изучить алгоритм Флойда для нахождения кротчайших путей в графе. Написать программу вычисления и отладить её. Провести эксперименты. Споставленной задачей справился успешно.

Постановка задачи.

Задан граф G=G(V,R), |V|=n. Каждому ребру графа (a,b)R a,bV поставлено в соответствие числу l(a,b), называемой длиной (весом) ребра (a,b). Если ребро (a, b) отсутствует, то считаем, что l(a,b)=+∞. Определим длину l(Pab) пути Pab из вершины a в вершину b, как сумму длин ребер, составляющих этот путь.

Задача отыскания кратчайшего пути для заданных вершин s,tV заключается в построении пути из s в t минимальной длины при условии, что такой путь существует. Обозначим такой путь P*st, пустой путь

Содержание работы

Цель, постановка задачи и алгоритм....3

Реализация алгоритма4

Программа...7

Результаты.43

Список литературы...48

Использованная литература

1. Э.Майника «Алгоритмы оптимизации на сетях и графах»
2. О.И.Мельников, В.А.Емеличев «Лекции по теории графов»
3. В.В.Фаронов «Delphi- программирование на языке высокого уровня»

Другие похожие работы

• Реферат - Теория информационных процессов
• Курсовая - Строительство модели аэродинамической трубы, в которой обдувается тело в форме самолета
• Курсовая - Реклама туристкого продукта в Интернет
• Курсовая - Решение задачи генетического алгоритма
• Контрольная - Составить линейную оптимизационную модель и решить ее при помощи надстройки «Поиск решения» в Excel
• Контрольная - Ответы на вопросы. Вариант 04
• Курсовая - Разработка консольных приложе-ний в среде Visual С++
• Курсовая - Численные методы решения систем дифференциальных уравнений
• Контрольная - Мультимедиа технологии
• Дипломная - Система поддержки принятия решений в управлении региональными целевыми программами