fy"> 4 (2), v 5 v 2 v < span align = "justify"> 3 v 4 (3).
В
Для заданого графа неможливо побудувати цикл
2б
В
Ідея алгоритму Уоршелла полягає в розширенні безлічі проміжних вершин за наступним правилом: на кожному кроці в розгляд додається одна нова вершина, після чого досяжності вершин перераховуються через неї. Якщо w - проміжна вершина, то досяжність вершини v з вершини u через w перераховується за правилом: D [u; v] = D [u; v] АБО (D [u; w] І D [w; v]). Таким чином, отримуємо матрицю досяжності:
В
Шляхи орієнтованого графа:
v 1 v 2 v 3 v 1 , v 1 v 2 , v 1 v 2 v 3 , v 1 v 2 v 3 v 4 , v 2 v 3 v 1 , v 2 v 3 v 1 v 2 , v 2 v 3 , v 2 v 3 v 4 , v 3 v 1 , v 3 v 1 v 2 ,
v
