Алгоритм SPF
Алгоритм SPF, основываясь на базе данных состояния связей, вычисляет кратчайшие пути между заданной вершиной S графа и всеми остальными вершинами. Результатом работы алгоритма является таблица, где для каждой вершины V графа указан список ребер, соединяющих заданную вершину S с вершиной V по кратчайшему пути.
Алгоритм SPF был предложен Е.В.Дейкстрой (E.W.Dijkstra).
Пусть
S - заданная вершина (источник путей);
E - множество обработанных вершин, т.е. вершин, кратчайший путь к которым уже найден;
R - множество оставшихся вершин графа (т.е. множество вершин графа за вычетом множества E);
O - упорядоченный список путей.
Описание алгоритма
1. Инициализировать E={S}, R={все вершины графа, кроме S}. Поместить в О все односегментные (длиной в одно ребро) пути, начинающиеся из S, отсортировав их в порядке возрастания метрик.
2. Если О пуст или первый путь в О имеет бесконечную метрику, то отметить все вершины в R как недостижимые и закончить работу алгоритма.
3. Рассмотрим P - кратчайший путь в списке О. Удалить P из О. Пусть V - последний узел в P.
Если V принадлежит E, перейти на шаг 2;
иначе P является кратчайшим путем из S в V (будем записывать как V:P); перенести V из R в E.
4. Построить набор новых путей, подлежащих рассмотрению, путем добавления к пути P всех односегментных путей, начинающихся из V. Метрика каждого нового пути равна сумме метрики P и метрики соответствующего односегментного отрезка, начинающегося из V. Добавить новые пути в упорядоченный список О, поместив их на места в соответствии со значениями метрик. Перейти на шаг 2.
Все вычисления производятся локально по известной базе данных, а потому - быстро по сравнению с дистанционно-векторными протоколами, при этом результаты получаются на основе полной, а не частичной информации о графе системы сетей.
Алгоритм SPF, основываясь на базе данных состояния связей, вычисляет кратчайшие пути между заданной вершиной S графа и всеми остальными вершинами. Результатом работы алгоритма является таблица, где для каждой вершины V графа указан список ребер, соединяющих заданную вершину S с вершиной V по кратчайшему пути.
Алгоритм SPF был предложен Е.В.Дейкстрой (E.W.Dijkstra).
Пусть
S - заданная вершина (источник путей);
E - множество обработанных вершин, т.е. вершин, кратчайший путь к которым уже найден;
R - множество оставшихся вершин графа (т.е. множество вершин графа за вычетом множества E);
O - упорядоченный список путей.
Описание алгоритма
1. Инициализировать E={S}, R={все вершины графа, кроме S}. Поместить в О все односегментные (длиной в одно ребро) пути, начинающиеся из S, отсортировав их в порядке возрастания метрик.
2. Если О пуст или первый путь в О имеет бесконечную метрику, то отметить все вершины в R как недостижимые и закончить работу алгоритма.
3. Рассмотрим P - кратчайший путь в списке О. Удалить P из О. Пусть V - последний узел в P.
Если V принадлежит E, перейти на шаг 2;
иначе P является кратчайшим путем из S в V (будем записывать как V:P); перенести V из R в E.
4. Построить набор новых путей, подлежащих рассмотрению, путем добавления к пути P всех односегментных путей, начинающихся из V. Метрика каждого нового пути равна сумме метрики P и метрики соответствующего односегментного отрезка, начинающегося из V. Добавить новые пути в упорядоченный список О, поместив их на места в соответствии со значениями метрик. Перейти на шаг 2.
Все вычисления производятся локально по известной базе данных, а потому - быстро по сравнению с дистанционно-векторными протоколами, при этом результаты получаются на основе полной, а не частичной информации о графе системы сетей.
