Условие:
Найти минимальный путь из вершины v1 в вершину v5 при помощи
алгоритма Форда-Беллмана для графа, заданного матрицей смежности:
0 4 2 0 0
4 0 1 5 6
2 1 0 3 8
0 5 3 0 3
0 6 8 3 0
Решение:
Ниже приведено пошаговое рассуждение на русском языке для нахождения минимального пути из вершины v1 в вершину v5 с использованием алгоритма Форда–Беллмана для данного графа с матрицей смежности. Входной граф задан матрицей (номера вершин: v1, v2, v3, v4, v5): v1: 0 4 2 0 0 v2: 4 0 1 5 6 v3: 2 1 0 3 8 v4: 0 5 3 0 3 v5: 0 6 8 3 0 Здесь ненулевые значения – это веса рёбер между соответствующими вершинами (0 означает отсутствие ребра). Граф симметричный, то есть неориентированный. 1. Инициализация. Задаём расстояния от источника (v1): d(v1) = 0, d(v2) = бесконечность, d(v3...