Алгоритм Уоршалла(да, фамилия пишется именно так) - EcsFlash/DataTypes GitHub Wiki

Суть(для чего он нужен вообще)

Для всех пар вершин (i, j) в данном графе алгоритм определяет, является ли вершина j достижимой из вершины i. Здесь достижимость означает, что существует путь из вершины i в j

Псевдокод

func WarshallAlgorithm(a [][]int) {
	for k := 0; k < len(a); k++ {
		for i := 0; i < len(a); i++ {
			for j := 0; j < len(a); j++ {
				if a[i][k] == 1 && a[k][j] == 1 {
					a[i][j] = 1
				}
			}
		}
	}
}

Пояснения: мы проходим по всем вершинам в матрице смежности(цикл с k), внутри этого цикла еще проходим по всем вершинам(i,j), и для каждой вершины ij пытаемся понять, есть ли путь i->k->j, если это так, ставим единицу в матрице.

Пример