Дипломная работа: Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделей

D[x]:=0; // Длина пути из источника x.

For w X do D[w]:=d[x,w]; // Инициализация матрицы расстояний

For k:=1 to n-2 do // Повторять n-2 раз

For w {X\{x}} do // Цикл по всем вершинам, кроме источника.

For u X do D[w]:=min(D[w],D[u]+d[u,w]); // выбор минимума.

End.

Этот алгоритм также основан на соотношении (принципе оптимальности) Беллмана. Всякий раз, когда находится путьчерез транзитную вершину u, который короче найденного пути из х в w, он заменяется на более короткий путь. Это соотношение должно проверяться для любой возможной из n-2 транзитных вершин при оценке пути в каждую вершину, поэтому в алгоритме имеется цикл, определенный в строке 4.

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

Идентификаторы :

d[s,t] – массив длин ребер графа для каждой пары вершин

s,t X. Если ребра нет, то соответствующий элемент этого массива содержит достаточно большое число.

х – вершина-источник графа <X,U>.

n=|X| - число вершин графа.

u,w – рабочие переменные.

D[w] – массив, в котором к концу работы алгоритма будут содержаться кратчайшие

длины путей из x в w для всех вершин w X.

BEGIN

D[x]:=0;

For w X do D[w]:=d[x,w];

T:={X\{x}};

While T=\= do

Begin

w:=вершина r из T такая, что D[r]=min{D[p]:p из T};

T:={T\{w}};

For u T do D[w]:=min[D[w],D[u]+d[u,w]];

End

END

Алгоритм Форда-Фалкерсона нахождения максимального потока в сети.

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