Содержание
Содержание
Основные понятия 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
С этим материалом также изучают
... отличие от алгоритма Дейкстры, алгоритм Беллмана — Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом. Список использованной литературы 1. ...
... имеющихся новостных интернет-каналов, примером которых является «LifeNews». Список источников информации1.Григорьев В. В. Книга и мировая ... в экономике (английский экономист У. Парето), использовавшей понятие о предельных величинах для широкого ...
... обстоятельств, исключающих преступность деяния 10 Список использованной литературы 15 Список использованной литературы 1. Беляев В.Г. Применение ... Комментарий к Уголовному кодексу Российской Федерации/ Авт. коллектив: Арендаренко А. В., Афанасьев Н. ...
... состоит из введения, трех глав, заключения и списка использованной литературы. 1.Конституция РФ 2.Венгеров А.Б. Теория государства ... совокупностью с большим выбором видов рекламы в Интернете, дают рекламодателям возможности подбора наиболее приемлемых ...
... в сфере массовой физкультурно-спортивной работы. Список использованной литературы Список используемой литературы 1. Агинако, Л. Обучение ... Обсуждение результатов исследования 38 Заключение 46 Список используемой литературы 48 Приложение Выдержка из ...
... направленные на реализацию миссии государства в области поддержки одаренных детей Список использованной литературы Список использованных источников Официальные документы 1. Федеральный государственный образовательный стандарт среднего ...
... 11. Сохранить документ с именем, содержащим свою фамилию, например: Иванов.doc. Список использованной литературы Список используемой литературы 1. «Планета информатики», учебник по информатике – http://www.inf1.info/modeling 2. ...
... PHP, SQL. Так же будут описаны средства разработки, используемые в данной работе и методы доступа к сайту. ... Такое положение дел обуславливает актуальность выбранной темы дипломного проектирования. Список литературы 1.Завадская Е.В. Ци Бай-ши. – М., ...
... не выделяя их. Алгоритм заканчивает свою работу, дойдя до конечной вершины, и весом кратчайшего пути становится вес конечной вершины. [3] Список использованной литературы Приложение Г. ...
... только человеку. Другое дело - реализация уже имеющегося алгоритма Список использованной литературы Слово "Алгоритм" происходит от algorithmi - ... жившего в 783-850 гг. В своей книге "Об индийском счете" он сформулировал правила ...