Нахождение кратчайшего пути в графе

Современные технологии позволяют упростить множество повседневных процессов. На данный момент автоматизация широко распространена и стремительно развивается, проникая практически во все области современного мироустройства. Стремительное развитие обусловлено высоким спросом, это говорит о том, что автоматизированы далеко не все процессы и список их постоянно растет.

Развитие автоматизации невозможно без качественно подготовленных кадров, а их подготовка требует изучения множества дисциплин. Одной из таких дисциплин является «Структуры и алгоритмы обработки данных». Этот предмет является одним из базовых, и без его изучения невозможно стать профессиональным разработчиком.

Целью данного курсового проекта, является подтверждение и укрепления знаний данного предмета, а если быть более точным выбор структур данных и алгоритмов их обработки, обоснование выбора, реализация выбранных алгоритмов обработки данных. Задачей является разработка программного средства, автоматизирующего заданный процесс.

1. Выбор языка программирования

Для написания программы я выбрал язык си++. C++ - компилируемый статически типизированный язык программирования общего назначения.

Поддерживает такие парадигмы программирования как процедурное программирование, модульность, раздельная компиляция, обработка исключений, абстракция данных, типы (объекты), виртуальные функции, объектно-ориентированное программирование, обобщенное программирование, контейнеры и алгоритмы, сочетает свойства как высокоуровневых, так и низкоуровневых языков. В сравнении с его предшественником — языком C, — наибольшее внимание уделено поддержке объектно-ориентированного и обобщённого программирования. Название «C++» происходит от названия языка C, в котором унарный оператор ++ обозначает инкремент переменной.

Являясь одним из самых популярных языков программирования, C++ широко используется для разработки программного обеспечения. Область его применения включает создание операционных систем, разнообразных прикладных программ, драйверов устройств, приложений для встраиваемых систем, высокопроизводительных серверов, а также развлекательных приложений (например, видеоигры). Существует несколько реализаций языка C++ - как бесплатных, так и коммерческих. Наиболее популярны проект GNU, Microsoft, Intel и Embarcadero (Borland). C++ оказал огромное влияние на другие языки программирования, в первую очередь на Java и C#.

При создании C++ Бьёрн Страуструп стремился сохранить совместимость с языком C. Множество программ, которые могут одинаково успешно транслироваться как компиляторами C, так и компиляторами C++, довольно велико — отчасти благодаря тому, что синтаксис C++ был основан на синтаксисе C.

Язык возник в начале 1980;х годов, когда сотрудник фирмы Bell Laboratories Бьёрн Страуструп придумал ряд усовершенствований к языку C под собственные нужды. До начала официальной стандартизации язык развивался в основном силами Страуструпа в ответ на запросы программистского сообщества. В 1998 году был ратифицирован международный стандарт языка C++: ISO/IEC 14 882:1998 «Standard for the C++ Programming Language»; после принятия технических исправлений к стандарту в 2003 году — нынешняя версия этого стандарта — ISO/IEC 14 882:2003.

Ранние версии языка, известные под именем «C с классами», начали появляться с 1980 года. Идея создания нового языка берёт начало от опыта программирования Страуструпа для диссертации. Он обнаружил, что язык моделирования Simula имеет такие возможности, которые были бы очень полезны для разработки большого программного обеспечения, но работает слишком медленно. В то же время язык BCPL достаточно быстр, но слишком близок к языкам низкого уровня и не подходит для разработки большого программного обеспечения. Страуструп начал работать в Bell Labs над задачами теории очередей (в приложении к моделированию телефонных вызовов). Попытки применения существующих в то время языков моделирования оказались неэффективными. Вспоминая опыт своей диссертации, Страуструп решил дополнить язык C (преемник BCPL) возможностями, имеющимися в языке Симула. Язык C, будучи базовым языком системы UNIX, на которой работали компьютеры Bell, является быстрым, многофункциональным и переносимым. Страуструп добавил к нему возможность работы с классами и объектами. В результате, практические задачи моделирования оказались доступными для решения как с точки зрения времени разработки (благодаря использованию Симула-подобных классов) так и с точки зрения времени вычислений (благодаря быстродействию C). В начале в C были добавлены классы (с инкапсуляцией), производные классы, строгая проверка типов, inline-функции и аргументы по умолчанию.

Разрабатывая C с классами (позднее C++), Страуструп также написал программу cfront — транслятор, перерабатывающий исходный код C с классами в исходный код простого C. Новый язык, неожиданно для автора, приобрёл большую популярность среди коллег и вскоре Страуструп уже не мог лично поддерживать его, отвечая на тысячи вопросов.

В 1983 году произошло переименование языка из C с классами в C++. Кроме того, в него были добавлены новые возможности, такие как виртуальные функции, перегрузка функций и операторов, ссылки, константы, пользовательский контроль над управлением свободной памятью, улучшенная проверка типов и новый стиль комментариев (//). Его первый коммерческий выпуск состоялся в октябре 1985 года. В 1985 году вышло также первое издание «Языка программирования C++», обеспечивающее первое описание этого языка, что было чрезвычайно важно из-за отсутствия официального стандарта. В 1989 году состоялся выход C++ версии 2.0. Его новые возможности включали множественное наследование, абстрактные классы, статические функции-члены, функции-константы и защищённые члены.

В 1990 году вышло «Комментированное справочное руководство по C++», положенное впоследствии в основу стандарта. Последние обновления включали шаблоны, исключения, пространства имён, новые способы приведения типов и булевский тип.

Стандартная библиотека C++ также развивалась вместе с ним. Первым добавлением к стандартной библиотеке C++ стали потоки ввода/вывода, обеспечивающие средства для замены традиционных функций C printf и scanf. Позднее самым значительным развитием стандартной библиотеки стало включение в неё Стандартной библиотеки шаблонов.

Никто не обладает правами на язык C++, он является свободным. Однако сам документ стандарта языка (за исключением черновиков) не доступен бесплатно.

2. Выбор алгоритма

Задача нахождения кратчайшего пути постоянно актуальна для водителей скорой медицинской помощи, бригад быстрого реагирования, милиции, спасателей… Перед каждым человеком, отправляющимся в путь, становится проблема выбора оптимального пути.

Анализ алгоритмов, применяемых в настоящее время для поиска кратчайших путей между вершинами графа, позволил выявить алгоритмы Уоршолла, Дейкстры, Форда. Все алгоритмы характеризуются разными вычислительными затратами и позволяют решать поставленную задачу, но наиболее эффективным считается алгоритм Дейкстры, предложенный в 1959 году.

Дейкстра разработал классический алгоритм для прохода по графам, грани которых имеют различный вес. На каждом шаге, он ищет необработанные узлы близкие к старту, затем просматривает соседей найденного узла, и устанавливает или обновляет их соответствующие расстояния от старта. Этот алгоритм имеет два преимущества по сравнению с поиском в ширину: он принимает во внимание длину пути и обновляет узлы, если к ним найден лучший путь.

3. Выбор типа данных и структуры программы

маршрут язык алгоритм программа

Данные этой задачи я представил в виде взвешенного неориентированного графа (Рис. 1).

Рис. 1. Схема городов, обслуживаемых компанией

Программа начинается с вызова функции main. Исходный код программы состоит из главного файла (Main). Для успешной компиляции необходимы стандартные библиотеки языка программирования Delphi. В главном файле программы содержится функция main. В модуле содержатся необходимые для работы программы функции.

4. Спецификация переменных и функций

Переменные:

const char file[]="c:\Goroda.txt" - имя файла на жестком диске, хранящим названия городов.

string from, to — начальная и конечная точки маршрута.

int w[N][N] - весовая матрица графа.

string g[N] - массив, хранящий список городов.

int *way — динамический массив для хранения маршрута.

Функции:

void Initial (string *Arr) — используется в программе для заполнения массива string g[] списком городов из файла file.

int *minimalLengthWay (int wm[N][N], int fromNode, int toNode, int *length, int *weight) — находит кратчайший путь в графе

5. Описание работы программы

После запуска программы на экран выводится список городов и расстояния между ними. Нужно будет ввести город отправления и город назначения.

После работы программы, на экране появится маршрут следования и длина пути.

6. Тестирование программы

Вывод список городов

Вывод расстояний между городами

Ввод данных

Вывод результата

1. Шилдт Герберт «Си ++. Руководство для начинающих, 2-е издание», М.; Издательский дом «Вильямс», 2005 г.

2. Кубенский А. А. «Структура и алгоритмы обработки данных: объектно-ориентированный подход и реализация на Си ++», Спб.; БХВ-Петербург, 2004 г.

3. Седжвик Роберт «Фундаментальные алгоритмы на Си++», К.; Издательство «ДиаСофт», 2001 г.

4. Уильям Топп, Уильям Форд «Структуры данных в Си ++», М.; ЗАО «Издательство БИНОМ», 1999 г.

Приложение А

Схема алгоритма

Приложение Б

Листинг программы

#include

#include

#include

#include

#include

#define N 12

const char file[]="c:\Goroda.txt" ;

void Initial (string *Arr) {

ifstream fin;

fin.open (file);

if (fin==NULL)

{

cout<<" Error open file" ;

system («Pause»);

exit (1);

}

int n=0;

fin>>Arr[n];

while (fin.good ())

{

n++;

fin>>Arr[n];

}

fin.close ();

}

int *minimalLengthWay (int wm[N][N], int fromNode, int toNode, int *length, int *weight){

int **minWeights; // Для хранения фронта волны

int i, j, k;

int *way; // Для хранения найденного пути и уже однажды пройденных вершин

bool find;

int tempLength;

int currNode;

minWeights = new int*[N];

for (i = 0; i < N; i++) {

minWeights[i] = new int[N];

}

way = new int[N];

for (i = 0; i < N; i ++)

for (j = 0; j < N; j ++)

minWeights[i][j] = -1;

for (i = 0; i < N; i ++)

way[i] = -1;

for (i = 0; i < N; i ++)

minWeights[fromNode][i] = 0;

find = false;

for (k = 0; k < N — 1; k ++) {

for (i = 0; i < N; i ++) {

tempLength = minWeights[i][k];

for (j = 0; j < N; j++) {

if (minWeights[j][k] ≠ -1 && wm[j][i] ≠ -1) {

if ((tempLength ≠ -1 && tempLength > minWeights[j][k] + wm[j][i]) || tempLength == -1) {

tempLength = minWeights[j][k] + wm[j][i];

}

}

}

minWeights[i][k+1] = tempLength;

}

}

find = minWeights[toNode][N-1] ≠ -1; // проверяем найден ли какй-либо путь

if (find) *weight = minWeights[toNode][N-1];

if (find) { // если путь найден — вычисляем его, но в обратной последовательности

j = 0;

way[0] = toNode;

currNode = toNode;

for (k = N — 2; k >= 0; k—) {

if (minWeights[currNode][k] ≠ minWeights[currNode][k + 1]) {

for (i = 0; i < N; i ++) {

if (minWeights[i][k] + wm[i][currNode] == minWeights[currNode][k + 1]) {

j++;

way[j] = i;

currNode = i;

break;

}

}

}

}

*length = j;

}

return way;

}

int main () {

SetConsoleCP (1251);

SetConsoleOutputCP (1251);

int i, j;

string from, to;

int f, t;

int *way;

int length, weight;

string g[N];

Initial (g);

int w[N][N]={0, 250,-1,320,-1,-1,-1,-1,-1,-1,-1,-1,

250,0, 300,-1,-1,-1,-1,-1,-1,-1,-1,-1,

— 1,300,0 ,-1,-1,-1,423,-1,-1,-1,-1,-1,

320,-1,-1,0, 640,412,830,-1,-1,-1,-1,-1,

— 1,-1,-1,640,0 ,-1,-1,550,-1,-1,-1,-1,

— 1,-1,-1,412,-1,0 ,-1,300,-1,-1,-1,-1,

— 1,-1,423,830,-1,-1,0, 520,540,580,-1,-1,

— 1,-1,-1,-1,550,300,520,0 ,-1,430,280,-1,

— 1,-1,-1,-1,-1,-1,540,-1,0, 400,-1,-1,

— 1,-1,-1,-1,-1,-1,580,430,400,0 ,-1,650,

— 1,-1,-1,-1,-1,-1,-1,280,-1,-1,0, 360,

— 1,-1,-1,-1,-1,-1,-1,-1,-1,650,360,0 };

cout << «Список городов, обслуживаемых компанией:» << endl << endl;

for (int i = 0; i < N; i++) {

cout<<< endl;

}

cout << endl;

for (int i = 0; i < N; i++) {

for (j = 0; j < i; j++) {

if (w[i][j]>0) {

cout << g[i] << «- «<< g[j] << «» << w[i][j] << «км «<< endl;

}

}

}

cout << endl;

cout << «Введите исходный город: «;

cin >> from;

cout << «Введите пункт назначения: «;

cin >> to;

for (i = 0; i < N; i++) {

if (g[i]==from) f=i;

if (g[i]==to) t=i;

}

way = minimalLengthWay (w, f, t, &length, &weight);

if (way[0] == -1)

cout << «Невозможно приготовить маршрут !» ;

else {

for (i = length; i >= 0; i—){

if (i ≠ length) cout << «-> «;

cout << g[way[i]];

}

cout << «nДлина пути: «<< weight << endl << endl;

}

system («Pause»);

return 0.