15336

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

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

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

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

Русский

2013-06-13

344.5 KB

32 чел.

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


 

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

57598. Культура Украины в XVI веке 67 KB
  Цель: определить условия и состояние развития культуры в Украине в XVI веке охарактеризовать влияние данных условий на развитие образования книгопечатания и искусства; развивать у учащихся умение самостоятельно работать с разными источниками информации...
57599. Окупаційний режим. Рух Опору в Україні 1.78 MB
  Головна увага викладача історії зосереджується на використанні нових педагогічних технологій, які б стимулювали пізнавальний інтерес до історії свого народу, його минулого та сучасного буття; відроджувати традиції свого народу; шанувати обряди та звичаї; аргументовано, на основі історичних фактів та свідчень очевидців відстоювати власні погляди на будь-яку проблему...
57600. Радянізація західних областей України у повоєнний період 88.5 KB
  Мета уроку: розкрити суперечливі складові та наслідки радянізації; розібрати особливості процесу відбудови в Західній Україні; формувати самостійне ставлення до складних історичних процесів, розуміння суперечності суспільного життя...
57601. ДЕРЖАВА З ЦЕНТРОМ У КИЄВІ. ПЕРШІ КНЯЗІ 94.5 KB
  І хоч Рюрик уже помер а його син Ігор поскандінавському Інґвар був ще замолодим щоб стати на чолі дружини Олег що був регентом опікуном доки Ігор не досягне повноліття зібрав дружину з варягів словян та фіннів узяв із собою Ігоря й поплив до Києва.
57602. Сталінська індустріалізація України. Друга і третя п’ятирічки 1.09 MB
  Мета уроку: Освітня: Визначити протиречиві тенденції 30х років Уяснити що друга і третя п’ятирічки були важливим етапом індустріалізації визначити дати другої та третьої п’ятирічок Визначити хронологічну послідовність головних подій...
57603. Україна – наш спільний дім 42 KB
  Обладнання: відеоматеріали: уривок з реклами Я їду додому адміністративна карта України фізична карта України; фотографії видатних людей вихідців з України; аудіозаписи пісен: С чего начинается Родина Україна у виконанні...
57604. Другий зимовий похід армії УНР. Припинення боротьби регулярних українських військ за незалежність України 59 KB
  Мета: проаналізувати мету та причини поразки Другого зимового походу армії УНР; пояснити значення Другого зимового походу як останньої збройної спроби відвоювати самостійність України та наслідки невдачі акції.
57605. Київська держава наприкінці Х – у першій половині ХІ ст 196.5 KB
  Відповідає та команда у якої швидше буде готова відповідь. За кожний правильний термін команда отримує 1 бал. Перша команда літера К. Друга команда літера С.
57606. Про що можна довідатися з сімейного фотоальбому. Родинне дерево 167 KB
  Мета: розкрити зміст науки генеалогія значення поняття родинне дерево; розвивати вміння роботи з фото джерелами створювати родинне дерево та визначити їх роль у роботі дослідників...