1 Разработка блок-схемы алгоритмов

На рисунке 1 представлена разработанная блок-схема алгоритма Флойда, где показано, каким образом, работает этот алгоритм. i, j, k, - аргументы прохода по циклу, N – размер массива расстояний, D[N][N] – массив расстояний.

Алг. Флойда

Ввод

і ,ј ,k,

N, D[N][N]

k=0,..,N

D[i][j]=min(D[i][j], D[i][k]+D[k][j])

D[i][k]<INF &&

D[k][j]<INF

i=0,…,N

j=0,…,N

Вывод

D[i][j]

нет

конец

да

Рисунок 1 – Блок-схема алгоритма Флойда

На рисунке 2 представлена разработанная блок-схема алгоритма Беллмана-Форда, где показано, каким образом, работает этот алгоритм. Smej – матрица смежности графа, start_v – начальная вершина, mRast – массив существующих в графе дуг, rez – массив кратчайших расстояний, RELAX(rez[mRast[j].to]) – улучшение пути между начальной и j-ой вершиной графа.

Конец

i=1..(n+1)

j=1..n

RELAX(rez[mRast[j].to])

i=1..n

rez[start_v]=0;

Ввод n, m, Smej[N][N], start_v

mRast[k].from=I;

mRast[k].to=j;

mRast[k].length=Smej[n][n];

k++;

Алгоритм Беллмана-Форда

Smej[n][n]!=0

j=1..n

rez[i]=1000000;

i=1..n

Ввод n, m, Smej[N][N], start_v

Рисунок 2 – Блок-схема алгоритма Беллмана-Форда

2 Разработка псевдокода

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

На рисунке 3 приведена часть псевдокода, где описан процесс ввода матрицы смежности заданного графа, где i, j – аргументы порхода по циклу. Тут же зануляется главныя диогональ при помощи условия – if(i==j), SizeMatr – размер матрицы(количество вешин в графе).

Рисунок 3 – Ввод матрицы смежности

На рисунке 4 приведена часть псевдокода, где описано вычисление матрицы кратчаших путей; будем улучшать путь через k-ю вершину, если пойти из i в k, а из k в j выгоднее, чем пойти напрямую из i в j, то запоминаем этот путь.

Рисунок 4 – Алгоритм Флойда

На рисунке 5 приведена часть псевдокода, где описан вывод получившейся матрицы.

Рисунок 5 – Вывод матрицы

Алгоритм Беллмана-Форда.

На рисунке 6 приведена часть псевдокода, где производится ввод n – количество вершин в графе, m – количество дуг в графе, start_v – начальная вершина, Smej – матрица смежности графа G(n,m).

Рисунок 6 – Ввод матрицы смежности

На рисунке 7 приведена часть псевдокода, где mRast – массив типа struct, в котором регистрируются from – начальная вершина дуги, to – конечная вершина дуги и length – длина этой дуги.

Рисунок 7 – Массив длинн

Ниже, на рисунке 8, заполняется массив кратчайших путей до вершины i, изначально путь равен «бесконечности». Здесь бесконечность – это некоторое значение, заведомо превосходящее все возможные расстояния. Длина дуги к start_v приравнивается нулю.

Рисунок 8 – Заполнение массива

На рисунке 9 реализован, непосредственно алгоритм Беллмана-Форда. Здесь rez[mRast[j].from] – длина пути из начальной вершины до вершины, от которой начинается текущая дуга, mRast[j].length – длина текущей дуги, rez[mRast[j].to] – текущее кратчайшее расстояние из start_v до j-ой вершины.

Рисунок 9 – Алгоритм Беллмана-Форда

В последней части псевдокода, рисунок 10, осуществляется вывод кратчайших расстояний, при этом, в случае если rez[i]=100000 путь до j-ой вершины не определен.

Рисунок 10 – Вывод кратчайших расстояний