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

z обозначим D(x,z).

Очевидно, если кратчайший путьиз x в z существует и проходит через промежуточную вершину w, то D(x,z) = D(x,w) + D(w,z). Эта формула справедлива для любой промежуточной вершины w рассматриваемого пути, в том числе и для последней, смежной с конечной вершиной w. Поэтому кратчайший путь можно отыскать, последовательно переходя от конечной вершины z в ближайшую смежную и запоминая цепочку построенных вершин (конечно, при условии, что хотя бы один путь между вершинами x и z существует и граф не содержит циклов. Эта идея и является в сущности принципом Р.Беллмана .

1.2. Графовые алгоритмы

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

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

D[w] – рабочий массив, при вычислениях интерпретируется как кратчайшая длина из вершины w в вершину z.

wX.

d[s,t] – массив длин ребер графа для каждой пары вершин s,t X. Если некоторое ребро отсутствует, то в элементе этого массива полагается записанным некоторое достаточно большое число, превышающее сумму длин всех ребер графа. 

Stack – последовательность вершин, определяющая кратчайший путь из x в z.

Begin

Stack:=’’; // Очистить Stack.

Stack <=z; // Поместить в стек конечную вершину z.

w:=z; // Запомнить первую пройденную вершину.

D[z]:=0; // Обнуление длины пути из вершины z в нее же.

While w=/=x do // Пока не будет достигнута начальная вершина, выполнять

// перебор вершин графа

p:= вершина, для которой величина D[p] = d[p,w]+D[w] минимальна. Если таких вершин несколько и среди них имеется вершина x, то p:=x, если же среди них нет вершины x – взять любую из доставляющих минимум сумме.

Stack <=p; // Записать выбранную вершину в стек.

w:=p; // и взять ее для построения следующего шага.

End;

End.

Пусть число вершин графа |X|=n, а число ребер |U|=m. Оценим сложность этого алгоритма как число шагов выполнения алгоритмической схемы, считая одним шагом выполнение ровно одного выполнимого оператора, каковые представлены только строками 2,3,4,5,6,8,9. В худшем случае выбор вершины в строке 8 (по минимуму расстояния) произойдет в результате просмотра всех n вершин, а цикл с заголовком в строке 6 повторится для всех вершин, поэтому сложность алгоритма можно оценить как C*n^2, где С – некоторая константа, учитывающая реализацию алгоритма в произвольной вычислительной среде.

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

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

Идентификаторы : d[s,t] – массив длин ребер графа для каждой пары вершин s,t X. Если ребра нет, то соответствующий элемент этого массива содержит достаточно большое число.

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

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

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

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