Компьютерные сети. 6-е изд.

Концепция кратчайшего пути (shortest path) требует некоторого пояснения. Один из способов измерения длины пути состоит в подсчете количества транзитных участков. В этом случае пути ABC и ABE на илл. 5.7 имеют одинаковую длину. Можно измерять расстояния в километрах. Тогда получается, что ABC гораздо длиннее, чем ABE (предполагается, что рисунок изображен с соблюдением пропорций).

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

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

Известно несколько алгоритмов вычисления кратчайшего пути между двумя узлами графа. Один из них был создан знаменитым Дейкстрой (Dijkstra) в 1959 году. Алгоритм находит кратчайшие пути между отправителем и всеми

Илл. 5.7. Первые шесть шагов вычисления кратчайшего пути от A к D. Стрелка указывает на рабочий узел

возможными получателями в сети. Каждому узлу присваивается метка (в скобках), означающая длину наилучшего известного пути до узла отправителя. Эти расстояния должны быть неотрицательными; условие выполняется, поскольку расстояния основаны на реальных величинах — пропускной способности или времени задержки. Изначально маршруты неизвестны, поэтому все узлы помечаются символом бесконечности. По мере работы алгоритма и нахождения путей метки узлов меняются, показывая оптимальные маршруты. Метка может быть постоянной или временной. Сначала все они являются временными. Когда выясняется, что метка действительно соответствует кратчайшему пути, она становится постоянной и в дальнейшем не изменяется.

Чтобы показать, как работает этот алгоритм, рассмотрим взвешенный ненаправленный граф на илл. 5.7 (а), где весовые коэффициенты отражают, например, расстояние. Нужно найти кратчайший путь от A к D. Для начала мы черным кружком помечаем узел A как постоянный. Затем исследуем все соседние с ним узлы, указывая около них расстояние до A. При обнаружении более короткого пути к какому-либо узлу вместе с указанием расстояния в метке меняется и узел, через который этот путь проходит. Таким образом, позже можно восстановить весь маршрут. Если в сети несколько кратчайших путей от A до D, то, чтобы их найти, нужно запомнить все узлы, через которые можно пройти к узлу, преодолев одинаковое расстояние.

#define MAX_NODES 1024                   /* максимальное количество узлов */

#define INFINITY 1000000000              /* число, превышающее длину максимального пути */

int n, dist[MAX_NODES][MAX_NODES];       /* dist[i][j] – это расстояние от i до j */

void shortest_path(int s, int t, int path[])

{ struct state {                         /* рабочий путь */

      int predecessor;                   /* предыдущий узел */

      int length;                        /* расстояние от источника до этого узла */

      enum {permanent, tentative} label; /* метка состояния */

} state[MAX_NODES];

int i, k, min;

struct state *p;

for (p = &state[0]; p < &state[n]; p++) { /* инициализация состояния */

      p->predecessor = –1;

      p->length = INFINITY;

      p->label = tentative;

}

state[t].length = 0; state[t].label = permanent;

k = t;                                  /* k – начальный рабочий узел */

do {                                    /* Есть ли лучший путь от k? */

      for (i = 0; i < n; i++)            /* У этого графа n узлов */

             if (dist[k][i] != 0 && state[i].label == tentative) {

                    if (state[k].length + dist[k][i] < state[i].length) {

                          state[i].predecessor = k;

                          state[i].length = state[k].length + dist[k][i];

                    }

             }

      /* Поиск узла, предварительно помеченного наименьшей меткой */

      k = 0; min = INFINITY;

      for (i = 0; i < n; i++)

             if (state[i].label == tentative && state[i].length < min) {

                    min = state[i].length;

                    k = i;

             }

      state[k].label = permanent;

} while (k != s);

/* Копирование пути в выходной массив */

i = 0; k = s;

do {path[i++] = k; k = state[k].predecessor; } while (k >= 0);

}

Илл. 5.8. Алгоритм Дейкстры для вычисления кратчайшего пути по графу

Проверив все соседние с A узлы, мы просматриваем временно помеченные узлы во всем графе и делаем узел с наименьшей меткой постоянным (илл. 5.7 (б)). Он становится новым рабочим узлом.