15336

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

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

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

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

Русский

2013-06-13

344.5 KB

31 чел.

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