Алгоритмизация

Рис 2: Блок-схема.

Пояснения к блок-схеме:

1. Задание входных данных.

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

б) Программа предлагает ввести начальную вершину i дерева кратчайших путей.

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

г) Вывод матрицы смежности на экран, в табличном виде.

2. Инициализация выходных данных (массивы: кратчайших путей – l и предков – ftr).

а) Если существует дуга (i,j), то выполняется пункт б, иначе пункт в.

б) Расстояние от i до j – вес дуги (i,j).

в) Расстояние от i до j – бесконечно велико.

г) Предком всех вершин графа становиться начальная вершина i.

3. Построение дерева кратчайших путей в графе.

а) Если существует дуга (c,j), то существует путь i->c->j.

б) Если весовая величина пути i->c->j меньше уже установленного расстояния от вершины i до j, то выполняется пункт в, иначе к пункту г.

в) Предком вершины j становится промежуточная вершина c, а расстояние от i до j сумма весов дуг пути i->c->j.

г) Для рассмотрения берётся следующая после вершина после вершины j – j+1.

д) Если все вершины занесены в дерево, то производится вывод на экран выходных данных, если нет, то происходит переход к пункту а.