IX Международная студенческая научная конференция Студенческий научный форум - 2017

Теория о нахождении кратчайших путей в последнее время интенсивно развивается. Наиболее распространенные методы решения задач данной теории – это использование алгоритмов: Дейкстры (для нахождения кратчайшего пути между двумя вершинами), Флойда (для нахождения кратчайших путей между всеми парами вершин) и Йена (для нахождения k – кратчайших путей в графе).

Граф на плоскости или в пространстве это несколько точек, где некоторые пары точек соединяются линиями. Но не всегда удобно задавать граф в том виде, как это указано в определении. Например, при обработке графа на компьютере, его удобно представлять в виде матрицы (двумерного массива). Разработку программы целесообразно реализовать в среде визуального объектно-ориентированного программирования wxDev-C++.

Опишем пошаговый алгоритм Дейкстры:

1. В цикле от 1 до N заполнить нулями массив A (инициализация); заполнить числом i массив C; перенести i-ю строку матрицы D в массив B, A[i]:=1; C[i]:=0 (i – номер стартовой вершины).

2. Найти минимум среди неотмеченных (т. е. тех k, для которых A[k]=0); пусть минимум достигается на индексе j, т. е. B[j]B[j]+D[j,k], то (B[k]:=B[j]+D[j,k]; C[k]:=j. Условие означает, что путь Vi ... Vk длиннее, чем путь Vi...Vj Vk.

3. Теперь надо перечислить вершины, входящие в кратчайший путь. Путь от Vi до Vk выдается в обратном порядке следующей процедурой:

   1. z:=C[k].

   2. Выдать z.

   3. z:=C[z]. Если z = 0, то конец, иначе перейти к 3.2.

Для выполнения алгоритма нужно N раз просмотреть массив B из N элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность: O(n²).

Код для цитирования: Скопировать