Файл: Точек, являющихся образом множества объектов, и множества линий.docx

Далее показан пошаговый процесс формирования остова минимального веса:

x2		x2			x2		x4		x2		x4
l3		l3	l7		l3	l7	l5		l3	l7	l5
x3		x3	x9		x3	x9	x5		x3	x9	x5
									l6
									x8

---

x2

x4

x2

x4

x2

x4

l3

l7

l5

l3

l7

l5

l2

l3

l7

l5

x3

x9

x5

x3

x9

x5

x1

x3

x9

x5

l6

l8

l6

l8

l6

l8

x8

x6

x8

x6

x8

x6

l10

l10

x7

x7

---

На следующем шаге итерации должно быть выбрано ребро с длиной l₁₂, которое соединяет вершины x₈ и x₉, однако в этом случае появился бы цикл в графе, поэтому данное ребро отбрасывается.

x2

x4

l2

l3

l7

l5

x1

x3

x9

x5

l6

l4

l8

x8

x6

l10

x7

---

Ребра с длинами l₁ и l₉ также игнорируются по причине образования ими циклов в графе.

Поскольку все вершины исходного графа выбраны, формирование остова минимального веса завершено.

Общую длину остова предлагается подсчитать самостоятельно.

---

3.3. Поиск кратчайших путей в графе

Подобные задачи возникают в компьютерных сетях и транспортных системах:

1. 
   в сетях определяется состав и структура сетевых протоколов для обслуживания движения пакетов информации: по данным о загрузке каналов, направлении и протяженности вычисляется наиболее оптимальный маршрут прохождения пакета информации; затем к пакету добавляется в заголовок перечень узлов для перехода от вершины х_i к вершине х_j или очередная вершина перехода;
   
2. 
   в транспортных системах определяется наиболее экономный по стоимости или по времени маршрут движения транспортной единицы.
   

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

Исходные данные для решения задачи берутся из двух матриц:

1. 
   матрицы весов l: ее структура аналогична матрице смежности, но вместо 1 и 0 задаются длины ребер, если вершины смежны, или ставится символ  в противном случае. В процессе решения задачи матрица весов преобразуется в матрицу кратчайших путей;
   
2. 
   матрицы переходов ν (ню), структура которой аналогична матрице смежности, но столбцы заполняются своими названиями. В процессе решения задачи она фиксирует формируемые маршруты минимальной длины между всеми парами вершин и преобразуется в итоге в матрицу кратчайших переходов.
   

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

Базовая вершина x_p позволяет:

1. 
   вычислять путь из вершины x_iв вершину x_jчерез вершину x_pпо формуле (l_ip + l_pj),
   
2. 
   сравнивать полученный результат с имеющимся значением l_ij,
   
3. 
   выбирать наименьшее значение.
   

---