15336

Изучение алгоритма Дейкстры и реализация его для заданного графа на языке программирования С++

Лабораторная работа

Информатика, кибернетика и программирование

Лабораторная работа №1 по дисциплине Структуры и алгоритмы обработки данных Цель работы: Изучение алгоритма Дейкстры и реализация его для заданного графа на языке программирования С. Алгоритм Дейкстры англ. Dijkstras algorithm алгоритм на графах изобретённый н

Русский

2013-06-13

344.5 KB

36 чел.

Лабораторная работа №1

по дисциплине

«Структуры и алгоритмы обработки данных»

Цель работы:

Изучение алгоритма Дейкстры и реализация его для заданного графа на языке программирования С++.

Алгоритм Дейкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.

Задание на работу

  1.  Написать программу, генерирующую граф согласно варианта.
    1.  Реализовать функцию поиска кратчайшего пути к вершине по алгоритму Дейкстры.
      1.  Искомая вершина должна задаваться через пользовательский интерфейс.
      2.  Оценить сложность алгоритма программы.
      3.  Представить граф как в графическом виде, так и в виде матриц.

Количество вершин: 12

Количество рёбер: 12

Вес рёбер:

  •  1, 4, 6, 8, 10, 12 = от 3 до 7
    •  2 = от 10 до 12
    •  3, 11 = от 6 до 8
    •  5 = от 5 до 9
    •  7 = от 1 до 2
    •  9 = от 1 до 3

Граф в графическом виде

Граф в матричном виде

Реализация программы на C++

// graph.cpp: определяет точку входа для консольного приложения.

//

#include "stdafx.h"

#include <iostream>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int tops = 12;

const int edges = 12;

const int infinity = 999;

void output_graph(int g[tops][edges]);

void generate_graph(int g[tops][edges]);

int weight(int n);

void dijkstra(int g[tops][edges], int start, int end);

void bestWay(int start, int current, int marks[tops], int g[tops][edges]);

void listOfedges(int g[tops][edges]);

int _tmain(int argc, _TCHAR* argv[])

{

srand(time(NULL));

int graph [tops][edges];

for(int i=0; i<tops; i++)//инициализация матрицы

 for(int j=0; j<edges; j++)

 {

  graph[i][j] = 0;

 }

generate_graph(graph);

output_graph(graph);

listOfedges(graph);

 

int a, b;

cout << "Enter first top (from 1 to 12): ";

cin >> a;

cout << "Enter last top (from 1 to 12): ";

cin >> b;

if (a == b)

 cout << "First top and the last top does not have to be equal." << endl;

else if (a < 1 || b < 1 || a > tops || b > tops)

 cout << "Invalid value entered" << endl;

else

 dijkstra(graph,a-1, b-1);

system("PAUSE");

return 0;

}

void dijkstra(int g[tops][edges], int start, int end)

{

bool visited[tops];

int marks[tops];

int current = start;

for (int i=0; i < tops; i++)//инициализция массивов

{

 visited[i] = false;

 marks[i] = infinity;

 }

marks[current] = 0;//метка первой вершины = 0

for (int x = 0; x < tops; x++)//цикл по количеству вершин

{

 visited[current] = true;//теперь текущая вершина посещена

 //*****************************

 //исследуем текущую вершину

 //*****************************

 //ищем непосещённые смежные вершины и изменяем метки в них

 for (int top = 0; top < tops; top++)

 {

  //если вершина не посещена и она смежная с текущей //и это не текущая вершина

  if(!visited[top] && g[current][top] /*&& current != top*/)

   //если метка найденной вершины больше чем путь до текущей + вес инцидентного ребра

   if(marks[top] > marks[current] + g[current][top])

    //то метка этой вершины равна пути до текущей + вес ребра

    marks[top] = marks[current] + g[current][top];

 }

 //*****************************

 //ищем новую текущую вершину

 //*****************************

 int min = infinity;

 current = -1;

 for (int top = 0; top < tops; top++)

  //если вершина не посещена и её метка меньше

  if(!visited[top] && marks[top] < min)

  {

   min = marks[top];

   current = top;

  }

}

//*****************************

//выводим лучший путь

//*****************************

cout << "One of the shortest paths is: ";

bestWay(start, end, marks, g);

 cout << endl << endl;

}

//рекурсивная функция для вывода лучшего пути

void bestWay(int start, int current, int marks[tops], int g[tops][edges])

{

if (current != start)

{

 int min = infinity;

 int next = -1;

 for (int top = 0; top < tops; top++)

  if(g[current][top] && marks[top] <= min)//если вершина смежная и её метка меньше минимальной

  {

   min = marks[top];

   next = top;

  }

  bestWay(start, next, marks, g);

  cout << " -> ";

}

cout << current+1;

}

void generate_graph(int g[tops][edges])//генерация графа

{

int edge = 0;//номер ребра

bool check_tops[tops];//метки несоединённых вершин

for (int i = 0; i < tops; i++)

 check_tops[i] = false;

bool f = true;//флаг факта соединения

int previousTop = 0 + rand() % 11;//первая вершина

int nextTop = -1;//следующая вершина

check_tops[previousTop] = true;//начальную пометим соединённой

 for(int i = 1; i < tops; i++)//соединяем все вершины графа (итераций на 1 меньше, чем вершин).

 {

 do

 {

  f = true;

  nextTop = rand() % 12;

  if(!check_tops[nextTop])//если вершина не соединена

  {

   check_tops[nextTop] = true;

   f = false;

  }

 } while (f);

 

 g[previousTop][nextTop] = g[nextTop][previousTop] = weight(edge);//соединяем  

 edge++;

 previousTop = nextTop;

}

 

//соединили все вершины, ставим оставшиеся рёбра

 int x = 0;

int y = 0;

for(; edge < edges; edge++)

 {

 do

 {

  x = rand() % 12;//1я вершина для соединения

  y = rand() % 12;//2я вершина для соединения

 } while (x==y && g[x][y]);//пока вершины не равны и уже не соединены

 g[x][y] = g[y][x] = weight(edge);//соединяем

}

}

int weight(int n)

{

if (n == 0 || n == 3 || n == 5 || n == 7 || n == 9 || n == 11)//3-7

{

 return 3 + rand() % 5;

}

else if (n == 1)//10-12

{

 return 10 + rand() % 3;

}

else if (n == 2 || n == 10 )//6-8

{

 return 6 + rand() % 3;

}

else if (n == 4)//5-9

{

 return 5 + rand() % 5;

}

else if (n == 6)//1-2

{

 return 1 + rand() % 2;

}

else if (n == 8)//1-3

{

 return 1 + rand() % 3;

}

else

{

  cout << "this value is incorrect" << endl;

  return -1;

}

}

void output_graph(int g[tops][edges])

{

cout << "  ";

for(int i=0; i<tops; i++)//верхняя строка значений

{

 if (i<9)

  cout << ' ';

 cout << i+1 << ' ';

}

cout << endl<< endl;

 

for(int i=0; i<tops; i++)//вывод матрицы

{

 if (i < 9)

  cout << ' ';

 cout << i+1 << ' ';

 for(int j=0; j<edges; j++)

 {

  

  cout << g[i][j];

  if(g[i][j] < 10)

   cout << ' ';

  cout << ' ';

 }

 cout << endl << endl;

}

cout << endl;

}

void listOfedges(int g[tops][edges])

{

cout << endl << "        List of edges" << endl << "top-----*edge weight*-----top"<< endl<< endl;

for (int x = 0; x<tops;x++)

 for (int y = 0; y<tops; y++)

  if (g[x][y] && x > y)

   cout

   << ((x+1 < 10) ? " " : "" )

   << x+1

   << "----------*"

   << ((g[x][y] < 10) ? " " : "" )

   << g[x][y]

   <<"*----------"

   << ((y+1 < 10) ? " " : "" )

   << y+1

   << endl;

cout << endl;

}

Скриншот с результатами выполнения программы

Оценка сложности алгоритма по наихудшему случаю

Наихудшим случаем будет, если на рассмотрение взять полный граф. Пусть n — это количество вершин. В полном графе количество рёбер будет ровно n(n-1)/2. Основной цикл алгоритма выполняется n раз. Так же в каждой итераци цикла тратится n операций на нахождение минимума и  n(n-1)/2 на подсчёт длины пути до вершины. Тогда сложность алгоритма можно записать как:

O((n^2)+n(n-1)/2 = O(3*(n^2)/2-1/2) = O(n^2)

Вывод

Был изучен алогритм Дейкстры и реализован на языке программирования С++. Была оценена сложность алгоритма.


10

6

2

9

7

5

4

8

12

3

11

6

1

4

8

5

2

5

7

4

8

7

12


 

А также другие работы, которые могут Вас заинтересовать

36240. Структура моделей знаний: семантические сети. Примеры 43 KB
  Структура моделей знаний: семантические сети. Понятие семантической сети основано на древней и очень простой идее о том что память формируется через ассоциации между понятиями. Квиллиан предположил что наша способность понимать язык может быть охарактеризована некоторым множеством базовых понятий концептов Базовыми функциональными элементами семантической сети служит структура из двух компонентов узлов и связывающих их дуг. Узлы в семантической сети соответствуют объектам понятиям или событиям.
36241. Структура моделей знаний: фреймовые модели. Примеры 43 KB
  Структура моделей знаний: фреймовые модели. Термин фрейм был предложен Марвином Минским в 70е годы. В теории фреймов этот образ называют фреймом комнаты. В нем есть дырки незаполненные значения некоторых атрибутов например количество окон эти дырки называют слотами Таким образом можно дать определение фрейму как минимально возможному описанию сущности какого то явления события ситуации процесса или объекта.
36242. Формальная система в представлении знаний 36 KB
  Из множества формул выделяют подмножеств правильно построенных формул ППФ. определяется эффективная процедура позволяющая по данному выражению выяснять является ли оно ППФ в данной ФС. Выделено некоторое множество ППФ называемых аксиомами ФС. При этом должна иметься эффективная процедура позволяющая для произвольной ППФ решить является ли она аксиомой.
36243. Система нечетких рассуждений в представлении знаний 248 KB
  Они в свою очередь определены через некоторую базовую шкалу В и функцию принадлежности. Понятие принадлежности. Тогда х принадлежит А если существует функция: Основным отличием нечеткой логики от классической как явствует из названия является наличие не только двух классических состояний значений но и промежуточных: Функция принадлежности определяет субъективную степень уверенности эксперта в том что данное конкретное значение базовой шкалы соответствует определяемому нечеткому множеству. Методы получения функции принадлежности...
36244. Системы искусственного интеллекта. Понятия и определения. Архитектура, классификация моделей 38 KB
  В этой информационной модели окружающей среды реальные объекты их свойства и отношения между ними не только отображаются и запоминаются но и как это отмечено в данном определении интеллекта могут мысленно целенаправленно преобразовываться . При этом существенно то что формирование модели внешней среды происходит в процессе обучения на опыте и адаптации к разнообразным обстоятельствам . Под структурным подходом мы подразумеваем попытки построения ИИ путем моделирования структуры человеческого мозга. Основной моделируемой структурной...
36245. Распознавание образов: подходы 36 KB
  Ассоциативность памяти и задача распознавания образов Динамический процесс последовательной смены состояний нейронной сети Хопфилда завершается в некотором стационарном состоянии являющемся локальным минимумом энергетической функции ES. Невозрастание энергии в процессе динамики приводит к выбору такого локального минимума S в бассейн притяжения которого попадает начальное состояние исходный пред'являемый сети образ S0. Поскольку для двух двоичных векторов минимальное число изменений компонент переводящее один вектор в другой является...
36246. Персептрон Розенблатта: структура, алгоритм обучения 52 KB
  Персептрон Розенблатта: структура алгоритм обучения. С сегодняшних позиций однослойный персептрон представляет скорее исторический интерес однако на его примере могут быть изучены основные понятия и простые алгоритмы обучения нейронных сетей.Розенблаттом метод обучения состоит в итерационной подстройке матрицы весов последовательно уменьшающей ошибку в выходных векторах. Здесь темп обучения.
36247. Генети́ческий алгори́тм 57.5 KB
  Некоторым обычно случайным образом создаётся множество генотипов начальной популяции. Таким образом можно выделить следующие этапы генетического алгоритма: Задать целевую функцию приспособленности для особей популяции Создать начальную популяцию Начало цикла Размножение скрещивание Мутирование Вычислить значение целевой функции для всех особей Формирование нового поколения селекция Если выполняются условия останова то конец цикла иначе начало цикла. Создание начальной популяции Перед первым шагом нужно...
36248. Программные агенты: классификация, структура. Многоагентные системы 43.5 KB
  Классификация агентов. Классификация агентов типы агентов Простые Смышленые Интеллектуальные характеристики Автономное выполнение Взаимодействие с другими агентами и пользователями Слежение за окружением Способность использования абстракций Способность использования предметных знаний Возможность адаптивного поведения для достижения цели Обучение из окружения Терпимость к ошибкам Rel time исполнение ER взаимодействие С позиции изучаемой дисциплины нас прежде всего...