Графы. Таблица смежности

• Граф — математическая абстракция реальной системы любой природы, объекты которой обладают парными связями.

 

Пример. Пусть требуется найти расстояния от 1-й вершины до всех остальных.

Решение:

1. минимальная метка 1 и её соседями являются вершины 2, 3, 6, где вершина 2 имеет минимальный вес 7, 3 ― 9, а 6 ― 14;
2. минимальная метка 2 и её соседями являются вершины 3, 4, где вершина 3 имеет минимальный вес 17 (7 + 10), 4 ― 22 (7 + 15). Но вершина 3 имеет уже вес 9, который меньше 17, поэтому метка не меняется;
3. минимальная метка 3 и её соседями являются вершины 6, 4, где вершина 6 имеет минимальный вес 11 (9 + 2), 4 ― 20 (9 + 11);
4. минимальная метка 6 и её соседями являются вершина 5, где вершина 5 имеет минимальный вес 20 (9 + 2 + 9);
5. минимальная метка 4 и её соседями являются вершина 5, где вершина 5 имеет минимальный вес 26 (9 + 11 + 6). Но вершина 5 имеет уже вес 20, который меньше 26, поэтому метка не меняется.