Материал: Sb97309

Для графа, представленного на рис. 1.1, а, будут получены следующие векторы:

Для графа, представленного на рис. 1.1, б, последовательность векторов имеет вид

Деревья с минимальными путями, полученные в ходе выполнения алгоритма Дейкстры, представлены на рис. 2.1.

Рис. 2.1

11

По результатам выполнения алгоритма Дейкстры можно убедиться, что итоговые векторы D совпадают с последними столбцами матриц минимальных путей алгоритма Форда–Беллмана, поэтому можно восстановить последовательность вершин минимального пути аналогично (1.3). Следует отметить, что в векторе D не определено количество ребер, образующих минимальный путь, поэтому для восстановления вершин нужно использовать цикл с неопределенным числом итераций.

2.3. Алгоритм Флойда

Алгоритм Флойда, в отличие от рассмотренных ранее, определяет минимальные пути между всеми парами вершин в графе. Фактически алгоритм Флойда осуществляет последовательный перебор всех вершин, проверяя, проходит ли через вершину путь, более короткий, чем прочие пути.

Аналогичная задача может быть решена многократным применением алгоритма Форда–Беллмана или Дейкстры (последовательно задавая вершины графа как стартовые для поиска), однако реализация подобной процедуры потребовала бы значительных вычислительных затрат.

Реализация алгоритма Флойда сводится к формированию матрицы всех минимальных путей. Для неориентированного графа матрица будет симметричной, что позволяет сократить вычислительные затраты, заполняя только значения из верхнего (нижнего) треугольника матрицы.

Имея матрицу всех минимальных путей M, несложно восстановить порядок следования вершин любого пути. Исходной для алгоритма Флойда, как и раньше, является матрица весов (длин) L.

Рассмотрим алгоритм для общего случая (ориентированного графа с неотрицательными весами). Требуется выполнить следующие действия:

1. Проинициализировать матрицу M:

M 1 L .

i 1, , n , j 1, , n , k 2, , n ,

где n – количество вершин графа (порядок матриц L, M).

3. Для двух заданных вершин восстановить последовательность прохождения вершин, соответствующую минимальному пути, по соотношениям, аналогичным (1.3).

12

Матрицы минимальных путей, полученные с помощью алгоритма Флойда для графов, приведенных на рис. 1.1, имеют вид

У неориентированного графа матрица M 2 симметричная. Легко убедиться, что первая строка матриц по значениям идентична вектору D алгоритма Дейкстры или последним столбцом матрицы алгоритма Форда–Беллмана. Значит, по выражениям, аналогичным (1.3), можно восстановить порядок следования вершин, соответствующих минимальной длине пути. Более того, можно восстановить подобную последовательность для любых двух пар вершин, объединив их в матрицу, или таблицу, путей:

Элементами матриц wij являются индексы вершин, через которые нужно

пройти от вершины i до вершины j (индекс i-й вершины можно не указывать, так как он задан номером строки матрицы W). Для неориентированного графа достаточно заполнить только верхнюю треугольную область, так как матрица минимальных путей симметрична, пути взаимно обратны. Для ориентированных графов матрицы маршрутов нужно определять полностью.

13

Достоинством алгоритма Флойда является его простота, недостатком – время выполнения.

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

3. РАЗРАБОТКА БЛОК-СХЕМЫ АЛГОРИТМА

При проектировании алгоритмов используют специальные графические элементы, называемые графическими блоками. Результатом алгоритмизации решения задачи становится блок-схема алгоритма, состоящая из некоторой последовательности таких графических блоков.

Блок-схема – это последовательность блоков, предписывающих выполнение определенных операций, а также связей между этими блоками. Внутри блоков указывается информация об операциях, подлежащих выполнению. Конфигурация и размеры блоков, а также порядок графического оформления блок-схем регламентированы нормативными документами ГОСТ 19002–80 и ГОСТ 19003–80 «Схемы алгоритмов и программ». Наиболее часто используемые блоки, элементы связей между ними и краткое пояснение к реализации блоков представлены в [3].

При соединении блоков следует использовать только горизонтальные и вертикальные линии потоков. Горизонтальные линии, имеющие направление справа налево, и вертикальные потоки, направленные снизу вверх, обязательно должны быть помечены стрелками. Прочие потоки допускается оставлять непомеченными. Линии потоков должны быть параллельны линиям внешней рамки или границам листа.

При проектировании алгоритмов применяются следующие общие правила:

–в начале алгоритма должны находиться блоки ввода значений исходных данных;

–после ввода значений исходных данных могут следовать блоки обработки данных либо вызова подпрограмм, если алгоритм предусматривает обработку данных в модулях;

–в конце алгоритма должны располагаться блоки вывода значений выходных данных;

14

– в алгоритме должны присутствовать только по одному блоку начала и окончания [4].

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

4. ОСНОВНЫЕ КОНСТРУКЦИИ ЯЗЫКА MATLAB

4.1. Условия и циклы

Условные операторы необходимы для организации принятия решения в ходе выполнения программы.

Условный оператор if в общем случае проверяет несколько условий и записывается следующим образом:

if условие1 операторы1

elseif условие2

операторы2 elseif условие3

операторы3

….. else

операторы4 end

Операторы после else выполняются в случае, если все вышеперечисленные условия – ложные. Альтернативные ветви не являются обязательными частями оператора.

Оператор множественного выбора switch выбирает одну альтернативу из нескольких по равенству переменной выбора одному из выборки значений:

switch (переменная_выбора) case значение1,

операторы1

case { значение2, значение3, значение4,...} операторы2

...

otherwise,

операторы

end

15