Курсовой проект алгоритм дейкстры

  • 14 сент. 2011 г.
  • 3029 Слова
Содержание

Введение……………………………………………………………………...…………...3
1 Постановка задачи…….………………………………………………………………..4
1.1 Изучение предметной области.…………………………………………..………….4
1.2 Изучение аналогов…………………………………………………………...............4
1.3 Организационная сущность задачи……………..……………………….………….4
1.4 Построение диаграммы вариантов использования.…………..…...…...................5
1.5 Входная информация………………………………………………………………...6
1.6 Выходная информация…………………………………………………………….…6
2 Выбор программного средства реализации………………………………..................7
3 Проектирование ………………………… …..………………………………………...9
3.1 Разработка графического интерфейса………….…………………………………...9
4 Реализация……………………………………………………………………………..10
4.1Объектно-ориентированное программирование…………………..……...…….. .10
5 Описание применения программного средства…………………………………….13
5.1 Программные и системные требования…………………………………………...13
5.2 Руководство пользователя…………..……………………………………………...13
6. Возможное дальнейшее развитие программного средства.………………….…....17
Заключение……………………………………………………………………………...18Литература………………………………………………………………………………19
Приложение А Иерархия классов…………………….………..…...…….……………20
Приложение Б Диаграмма вариантов использования ...……..……..…..…………….21
Приложение В Диаграмма деятельности……….……………………..……...……….22
Приложение Г Листинг программного средства……………………..……………….23

Введение

Информатизация общества стала одной из важнейших характеристик нашего времени. Нет ни одной области человеческой деятельности, которая в той илииной степени не была связана с процессами получения и обработки информации. Информация стала важным инструментом политики и культуры, промышленности, науки и образования.
За последние годы произошел резкий скачок в развитии компьютерной техники и программного обеспечения персональных компьютеров, а также наблюдается значительное расширение сферы их применения. Компьютеры применяютсяпрактически во всех видах человеческой деятельности (промышленность, наука, медицина, образование, транспорт, банковское дело, связь, военная техника, бытовая техника и т.д.).
Когда перед человеком, не склонным к разработке собственных алгоритмов, встает задача поиска пути на карте, он пытается вспомнить все, чему его когда-то учили. Вспоминается с трудом, так как знания за ненадобностью имеют тенденциюулетучиваться. Но потом все же всплывает волшебное словосочетание “Алгоритм Дейкстры”. Этого достаточно, потому что остальную часть работы по “вспоминанию” берет на себя интернет. А если интернет кроме описания алгоритма, выдаст еще что-то типа “что алгоритм Дейкстра -- один из лучших”, то будущий автор приходит в восторг и больше ни о чем не думает.Алгоритм Дейкстры действительно достаточно эффективен.Он разработан для поиска пути в произвольном графе, когда о структуре графа ничего заранее неизвестно. Однако для частных случаев, как правило, можно разработать алгоритмы, которые будут более эффективны, чем общие. Например, для деления целых чисел очень эффективным является алгоритм деления столбиком. Но если делитель – степень двойки, а делимое представлено в двоичном виде, то значительно прощеполучить результат поразрядным сдвигом.
Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, чторасстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u...
tracking img