Описание теории графов. Алгоритм Флойда и Декстры.

Предпросмотр материала:

1/7

Описание теории графов. Алгоритм Флойда и Декстры.

Описание презентации по отдельным слайдам:

1 слайд

Курсовая робота:
по курсу «Кросс-платформенное программирование».
На тему:
«Разработка программы для отыскания кратчайшего пути на графе».
Выполнил: Коломиец Н.Ю.
Руководитель: Сукиасов В.Г.
2 слайд

Кроссплатформенное программное обеспечение-
программное обеспечение, работающее более чем на одной аппаратной платформе и/или операционной системе.
3 слайд

Кросс-платформа.

Языки
WEB
С,С++
Пере компилируемые
JAVA, C#
Интерпретируемые
PHP,perl,Ruby
4 слайд

Теория графов.
5 слайд

Сравнения алгоритма Дейкстры и алгоритма Флойда.
алгоритм Дейкстры
Очень быстра я работа;
Работает с дугами не отрицательного веса;
Сложен в реализации;
Ищет за один проход только длины из одной вершины до остальных;
Применяется в многих маршрутизаторах:

алгоритма Флойда
Работает медленно;
Прост в реализации;
Работает с отрицательными весами дуг;
Ищет за один проход сразу все длины кратчайших путей;
6 слайд

Интерфейс программы.
7 слайд

Спасибо за внимание.

Краткое описание материала

Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств. G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V×V.

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

Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез.

Описание теории графов. Алгоритм Флойда и Декстры.

Информатика

Другие методич. материалы

PPTX

08.01.2015

1373

Информатика

Другие методич. материалы

Файл будет скачан в формате:

PPTX

Автор материала

Коломиец Людмила Федоровна

учитель

На сайте: 10 лет и 10 месяцев
Всего просмотров: 12640
Подписчики: 0
Всего материалов: 5

12640
просмотров
5
материалов
0
подписчиков

Настоящий материал опубликован пользователем Коломиец Людмила Федоровна.
Инфоурок является информационным посредником. Всю ответственность за опубликованные материалы несут пользователи, загрузившие материал на сайт. Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете на материал.