15336

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

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

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

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

Русский

2013-06-13

344.5 KB

39 чел.

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


 

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

654. Расчет погонной массы груза, тягового органа и движущих частей конвейера 136 KB
  Нормативные значения расчетных величин. Основные параметры рабочего органа. Расчет погонной массы груза, тягового органа и движущих частей конвейера. Расчет тягового органа на прочность. Основные размеры тягового органа. Кинематический расчет. Выбор элемента передач.
655. Философия жизни и феноменология 130.5 KB
  Иррационализм А. Шопенгауэра. Мир как воля и представление. Философия жизни Ф. Ницше. Понятие жизнь и воля к власти. Иррационализм Ницше в теории познания. Представление о сверхчеловеке. Критика Ницше христианства. Интуитивизм и творческая эволюция А. Бергсона. Феноменология Э. Гуссерля. Разработка Гуссерлем онтологической и гносеологической проблематики. Понятие жизненного мира.
656. Статистическая проверка непараметрических гипотез 78 KB
  Нулевой непараметрической гипотезой называется гипотеза относительно общего вида функции распределения. К первой группе относятся критерии согласия, с помощью которых проверяются нулевые гипотезы относительно общего вида функции распределения.
657. Исследование линейной цепи с обратной связью 39 KB
  Экспериментально исследовать влияние обратной связи на частотные характеристики линейной цепи, а также устойчивость линейной цепи с обратной связью.
658. Проектирование широкополосного усилительного устройства 643.5 KB
  Структурная схема усилителя. Выбор рабочей точки и расчет параметров транзистора. Расчет входного усилительного каскада. Методы исследования, расчета и проектирования широкополосных усилителей гармонических сигналов и импульсных сигналов
659. Товароведная характеристика и экспертиза качества питьевого молока вырабатываемого и реализуемого ГУСП ПЗ Тополя предприятия Московский Тюменского района 410.5 KB
  Состав и потребительские свойства молока. Упаковка, маркировка, хранение и транспортирование питьевого молока. Изучение ассортимента молочных продуктов, вырабатываемых ГУСП ПЗ Тополя. Результаты токсиколого-гигиенических исследований качества молока. Обеспеченность предприятия основными средствами производства и трудовыми ресурсами.
660. Психология развития, возрастная психология 113.5 KB
  Предмет задачи и методы психологий развития. Психология обучения и развития. Психология дошкольного возраста. Методика исследования типологических особенностей личности (К. Юнг). Психология подросткового возраста. Методика исследования агрессивного поведения подростков (А. Бас и А. Даки.).
661. Теория макроэкономического равновесия 125 KB
  Макроэкономическое равновесие: совокупный спрос и совокупное предложение. Идеальная модель. Классическая и кейнсианская модели макроэкономического равновесия. Нисходящая кривая совокупного спроса объясняется другими факторами: (ценовые факторы).
662. Дефицитарность общения у детей и подростков 136.5 KB
  Ранний детский аутизм (клинические проявления). Дефицитарность общения при других видах психической патологии. Еще раз о дефицитарности общения при ранней детской шизофрении. Механизмы социальной и школьной дизадаптации, профилактика и коррекция при дефицитарности общения у детей и подростков.