Метод Дейкстры нахождения кратчайшей цепи в связном графе

курсовая работа

2.1 Программная реализация метода Дейкстры

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

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

Начальная расстановка отметок.

Полагаем

.

В качестве бесконечности принимаем очень большое число, такое, которое во много раз больше любой из длин ребер в исследуемом графе.

Все отметки объявляем предварительными.

Исправление отметок.

Среди всех предварительных отметок находим наименьшую. Пусть это отметка вершины . Для каждой вершины , смежной с и имеющей предварительную отметку, исправляем по следующему правилу:

.

После исправления отметок всех смежных с вершин объявляем отметку вершины окончательной.

Затем проводим построение кратчайшей цепи, стартую от вершины и заканчивая вершиной .

Делись добром ;)