Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделей — страница 3

  • Просмотров 3356
  • Скачиваний 310
  • Размер файла 184
    Кб

Алгоритм Беллмана поиска кратчайшего путимежду двумя вершинами связного графа, не имеющего циклов с неотрицательными длинами ребер. Его описание приводится ниже при помощи алгоритмической схемы. Идентификаторы : 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. Begin 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 // Цикл по всем вершинам,