Содержание
Содержание
Основные понятия 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