Содержание

Содержание

Основные понятия 3

Представление графов 5

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

Алгоритм Форда ‒ Беллмана на языке C++ 10

Результаты работы программы на примере 11

Список использованных источников 13

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

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

Используя описанный выше алгоритм, создадим программу на языке C++, которая будет получать орграф в виде списка смежности с дополнительным параметром (весом) для каждого ребра из текстового файла следующего формата: первая строка ‒ количество вершин графа, вторая ‒ количество рёбер графа, далее следуют строки с описанием каждого ребра

[начальная вершина] [конечная вершина] [вес ребра]

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

Список использованных источников

Алгоритмы: построение и анализ, 2-е издание [Книга] / авт. Томас Х. Кормен Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. — Москва : Издательский дом "Вильямс", 2005.

Интернет ссылка: http://libgen.info/view.php?id=906

Комбинаторика для программистов [Книга] / авт. В. Липский. — Москва : Издательство "Мир", 1988.

Интернет ссылка: http://libgen.info/view.php?id=32502

Структуры данных и алгоритмы [Книга] / авт. Альфред В. Ахо Джон Хопкрофт, Джеффри Д. Ульман. — Москва : Издательский дом "Вильямс", 2000.

Интернет ссылка: http://libgen.info/view.php?id=846

Теория графов Алгоритмический подход [Книга] / авт. Кристофидес Н.. — Москва : Издательство "Мир", 1978.

Интернет ссылка: http://libgen.info/view.php?id=3661

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