15336

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

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

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

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

Русский

2013-06-13

344.5 KB

41 чел.

Лабораторная работа №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


 

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

40122. Реляционная модель данных. Основные понятия: отношение, кортеж, домен. Получение нормальных форм отношений из диаграммы «сущность-связь». Реляционная алгебра и ее основные понятия 78 KB
  Реляционная модель данных отличается удобным для пользователя табличным представлением и доступом к данным. Она является совокупностью простейших двумерных таблиц – отношений. В реляционной модели достигается гораздо более высокий уровень абстракции данных, чем в иерархической или сетевой. Это обеспечивается за счет использования математической теории отношений (реляционная алгебра).
40123. Реляционная алгебра, основные операторы реляционной алгебры. Связь языка SQL с операторами реляционной алгебры 100.5 KB
  Основная идея реляционной алгебры состоит в том что коль скоро отношения являются множествами то средства манипулирования отношениями могут базироваться на традиционных теоретикомножественных операциях дополненных некоторыми специальными операциями специфичными для баз данных совокупность которых образует полную алгебру отношений. В состав теоретикомножественных операций входят операции: Объединения отношений. При выполнении операции объединения двух отношений производится отношение включающее все кортежи входящие хотя бы в одно из...
40124. Реляционная модель данных. Теория нормализации. Нормальные формы: первая, вторая, третья, Бойса-Кодда 50 KB
  Реляционная модель данных отличается удобным для пользователя табличным представлением и доступом к данным. В реляционной модели достигается гораздо более высокий уровень абстракции данных чем в иерархической или сетевой. К числу достоинств реляционного подхода можно отнести: наличие небольшого набора абстракций которые позволяют сравнительно просто моделировать большую часть распространенных предметных областей и допускают точные формальные определения оставаясь интуитивно понятными; наличие простого и в то же время мощного...
40125. Физическая организация баз данных. Файлы: последовательные, с прямым доступом, с хеш-адресацией, индексно-последовательные, В-деревья 78 KB
  Предполагается что для доступа к iой записи нужно просмотреть все i1 записи. Последовательный доступ с фиксированной длиной записи. Картинка i = 0 i 1L Если записи располагаются в оперативной памяти то это массив. Если записи расположены на диске то порядок ввода вывода данных зависит от языка программирования.
40126. Вычислительная машина 97.5 KB
  Машина Шикарда умела складывать и вычитать шестизначные числа оповещая звонком о переполнении. Оригинальная машина была утеряна до двадцатого столетия но в 1960 году была построена её точная работающая копия. Машина Паскаля позволяла выполнять не только сложение но и другие операции однако при этом требовала применения довольно неудобной процедуры повторных сложений.
40127. Операционная система 39.5 KB
  С 1990х наиболее распространенными операционными системами являются ОС семейства Microsoft Windows и UNIXподобные системы. Windows 2000 в полной мере использует возможности машин с несколькими процессорами. Windows 2000 способна закрепить каждый поток за отдельным процессором и тогда два потока исполняются действительно одновременно. Ядро Windows 2000 полностью поддерживает распределение процессорного времени между потоками и управление ими на таких системах.
40128. Языки программирования и их классификация 66 KB
  При первом способе его началом является пара символов а окончанием последний символ строки: Это комментарий При втором способе его началом является пара символов а окончанием пара символов: Еще один пример комментария В C различают три группы типов данных: фундаментальные типы встроенные типы и типы определяемые пользователем. Фундаментальные типы делятся на...