Графы-алгоритм Дейкстры

Санкт-Петербургский государственный Морской Технический Университет

(СПбГМТУ)

Факультет Морского приборостроения

Задание №1

Тема:

«Графы-алгоритм Дейкстры»

Выполнил: студент группы 3230

Матвиенко Анастасия

Проверил: преподаватель

Борисов Александр Николаевич

2018

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

       Пример использования графов – алгоритм Дейкстры нахождения кратчайшего пути во взвешенных графах.

Рассмотрим пример нахождения кратчайшего пути.  Дана сеть автомобильных дорог , соединяющих различные точки города ( г. Моршанск) . Найти кратчайший путь от данной начальной точки (1) до конечной данной (14). Для выполнения работы мы выбрали определённую часть города на карте и отметили на ней 14 точек. Затем измерили расстояние между ними.

[pic 1]

Рисунок 1 «Схема путей».

#define _CRT_SECURE_NO_WARNINGS

#include

#include

#include

using namespace std;

#define SIZE 14

int main()

{

        int a[SIZE][SIZE]; // матрица связей

        int d[SIZE]; // минимальное расстояние

        int v[SIZE]; // посещенные вершины

        int temp;

        int minindex, min;

        system("chcp 1251");

        system("cls");

        // Инициализация матрицы связей

        for (int i = 0; i

        {

                a[i][i] = 0;

                for (int j = i + 1; j

                        printf("vvedite rasstoyanie %d - %d: ", i + 1, j + 1);

                        scanf("%d", &temp);

                        a[i][j] = temp;

                        a[j][i] = temp;

                }

        }

        // Вывод матрицы связей

        for (int i = 0; i

        {

                for (int j = 0; j

                        printf("%5d ", a[i][j]);

                printf("\n");

        }

        //Инициализация вершин и расстояний

        for (int i = 0; i

        {

                d[i] = 100000;

                v[i] = 1;

        }

        d[0] = 0;

        // Шаг алгоритма

        do {

                minindex = 100000;

                min = 100000;

                for (int i = 0; i

                { // Если вершину ещё не обошли и вес меньше min

                        if ((v[i] == 1) && (d[i]

                        { // Переприсваиваем значения

                                min = d[i];

                                minindex = i;

                        }

                }

                // Добавляем найденный минимальный вес

                // к текущему весу вершины

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

                if (minindex != 100000)

                {

                        for (int i = 0; i

                        {

                                if (a[minindex][i] > 0)

                                {

                                        temp = min + a[minindex][i];

                                        if (temp < d[i])

                                        {

                                                d[i] = temp;