Долой негров - EcsFlash/DataTypes GitHub Wiki

Суть

Алгоритм Флойда — Уоршелла — алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования.

Псевдокод

func FloydWarshallAlgorithm(a [][]float64) {
        // кусок между этими комментариями нужен лишь для того, чтобы матрицу смежности с весами вместо едениц, перевести в матрицу "расстояний"
	infinity := math.Inf('+')
	for k := 0; k < len(a); k++ {
		for i := 0; i < len(a); i++ {
			if a[i][k] == 0 && i != k {
				a[i][k] = infinity
			}
		}
	}
        // дальше следует сам алгоритм, применяемый к матрице "расстояний"
	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] != infinity && a[k][j] != infinity {
					a[i][j] = min(a[i][k]+a[k][j], a[i][j])
				}
			}
		}
	}
}

image