Рис 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.
д) Если все вершины занесены в дерево, то производится вывод на экран выходных данных, если нет, то происходит переход к пункту а.