WikiSort.ru - Программирование

Шаг 1

Пронумеровать вершины исходного графа целыми числами от ${\displaystyle 1}$ до ${\displaystyle N}$ . Сформировать матрицу ${\displaystyle D_{}^{0}}$ (размерностью ${\displaystyle N\times N}$ ), каждый элемент ${\displaystyle i}$ , ${\displaystyle j}$ которой ${\displaystyle d_{ij}^{0}}$ определяет длину кратчайшей дуги ведущей из вершины ${\displaystyle i}$ в вершину ${\displaystyle j}$ . В отсутствие такой дуги положить ${\displaystyle d_{ij}^{0}=\infty }$ .

Шаг 2

Здесь через ${\displaystyle D_{}^{m}}$ обозначается матрица размерностью ${\displaystyle m\times m}$ с элементами ${\displaystyle d_{ij}^{m},m=1,2,...,N}$ . Последовательно определить элементы матрицы ${\displaystyle D^{m}}$ из элементов матрицы ${\displaystyle D^{m-1}}$ для ${\displaystyle m}$ принимающих значения ${\displaystyle 1,2,...N}$ :

${\displaystyle d_{mj}^{m}=min_{i=1,2,...m-1}(d_{mi}^{0}+d_{ij}^{m-1})~(j=1,2,...,m-1)}$

${\displaystyle d_{im}^{m}=min_{j=1,2,...m-1}(d_{ij}^{m-1}+d_{jm}^{0})~(i=1,2,...,m-1)}$

${\displaystyle d_{ij}^{m}=min(d_{im}^{m}+d_{mj}^{m},d_{ij}^{m-1})~(i,j=1,2,...,m-1)}$

Кроме того, для всех i и m положить ${\displaystyle d_{ii}^{m}=0}$ .