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

Содержание

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

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

Программа…7

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

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

Выдержка из текста

Цель работы.

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

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

Задан граф 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, пустой путь

Список использованной литературы

1.Э.Майника «Алгоритмы оптимизации на сетях и графах»

2.О.И.Мельников, В.А.Емеличев «Лекции по теории графов»

3.В.В.Фаронов «Delphi- программирование на языке высокого уровня»

С этим материалом также изучают

Нахождение наикратчайшего пути в графе

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

Поиск кратчайших путей в графе (С++)

... FloydWarshall, выполняющая нахождение кратчайших путей между вершинами графа. После выполнения подпрограммы FloydWarshall в цикле для каждой пары вершин печатается заголовок, кратчайшее расстояние между вершинами (если путь существует), а ...

Для заданного на рисунке графа постройте минимальное остовное дерево, применив алгоритм Прима (построение начинать с вершины Е). В ответе укажите порядок в

... из текстаДля заданного на рисунке графа постройте минимальное остовное дерево, применив алгоритм Прима (построение начинать с вершины Е). В ответе укажите порядок включения ребер.

Применение муравьиных алгоритмов для решения задачи коммивояжера в дипломных работах

Изучите все аспекты применения муравьиных алгоритмов (ACO) для задачи коммивояжера. Статья содержит теорию, обзор вариаций (ACS, MMAS) и гибридных методов для дипломной.

Экспериментальное сравнение трудоемкости двух алгоритмов решения задачи построения наибольшего паросочетания минимального веса в двудольном графе

... алгоритма решения задачи построения наибольшего паросочетания минимального веса в двудольном графе и проведении экспериментальной оценки трудоемкости этих двух алгоритмов. Один из алгоритмов использует алгоритм решения транспортной задачи. ...

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

... языке. Решение задачи опре-деления кратчайшего пути принадлежит к числу сложных комбинаторных задач, называемых трудно-решаемыми.Для решения задачи трассировки разработано множество алгорит-мов, например, алгоритм Ли ...

Постановка и разработка алгоритма решения задачи Учёт основных средств

... ВХОДНАЯ ИНФОРМАЦИЯ 13 4. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ 18 4.1 Укрупненная блок-схема решения задачи 18 4.2 Структура программного ... ВХОДНАЯ ИНФОРМАЦИЯ 13 4. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ 18 4.1 Укрупненная блок-схема решения задачи 18 4.2 Структура программного ...

Постановка и разработка алгоритма решения задачи Учёт основных средств 2

... ВХОДНАЯ ИНФОРМАЦИЯ 13 4. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ 18 4.1 Укрупненная блок-схема решения задачи 18 4.2 Структура программного ... ВХОДНАЯ ИНФОРМАЦИЯ 13 4. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ 18 4.1 Укрупненная блок-схема решения задачи 18 4.2 Структура программного ...

Управление путем ранжирования стратегических задач

Содержание Введение…………………………………...………………………………………3 1. Управление путем ранжирования стратегических задач …………………...5 2. Управление стратегическими задачами .………………………………..……7 Заключение……………………………………………………………………….11 Список использованной литературы ...

Похожие записи