Условие:
Найти минимальный путь из вершины 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 означает отсутствие ребра). Граф симметричный, то есть неориентированный.
- Инициализация. Задаём расстояния от источника (v1): d(v1) = 0, d(v2) = бесконечность, d(v3...