Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности.
Глава 1. Теоретическая часть 1.1 Алгоритм Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг 1.2 Задача с методическим описанием 1.3 Алгоритмизация задачи Глава 2. Практическая часть Задание 1 Задание 2 Задание 3 Задание 4 Задание 5 Задание 6 Задание 7 Задание 8 Заключение Список использованной литературы Введение История человечества насчитывает много миллионов лет. Метод Дейкстры нахождения кратчайшей цепи в связанном графе является, пожалуй, самым удачным из методов минимизации, применение которых обеспечивает отыскание таковой цепи в графе. Глава 1. Теоретическая часть 1.1 Алгоритм Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг Пусть дан граф G=(X, Г), дугам которого приписаны веса (стоимости), задаваемые матрицей C=[cij]. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины s X до заданной конечной вершины t X, при условии, что такой путь существует, т.е. при условии t R(s). Элементы cij матрицы весов C могут быть положительными, отрицательными или нулями. Наиболее эффективный алгоритм решения задачи о кратчайшем (s - t) - пути первоначально дал Дейкстра.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
