Најкраћи путеви измећу свих парова чворова

Уколико желимо да одредимо најкраће путеве између свих парова чворова можемо покренути Дајкстрин алгоритам из сваког чвора у графу, а можемо употребити и неки од специјализованих алгоритама за проналажење свих најкраћих путева. Један од најпознатијих путева тог типа је Флојд-Варшалов алгоритам. Након \(k\) корака алгоритма претпоставићемо да су познате најкраће дужине путева између свих чворова, при чему се на тим путевима као међучворови могу користити само чворови из скупа \(V_k = \{0, 1, \ldots k-1\}\). У сваком наредном кораку додајемо чвор \(k\) и пошто сада анализирамо путеве између чворова \(i\) и \(j\) који могу водити преко чворова \(V_{k+1} = \{0, 1, \ldots, k\}\), упоређујемо дужину пута између та два чвора који не иде преко чвора \(k\) већ само преко чворова из \(V_k\) (ту дужину већ знамо) и дужину која иде преко чвора \(k\) која је једнака збиру дужина најкраћег пута од \(i\) до \(k\) преко \(V_k\) и најкраћег пута од \(k\) до \(j\) преко \(V_k\) (обе ове дужине већ знамо). У случају да се дужине свих најкраћих путева чувају у матрици, Флојд-Варшалов алгоритам се веома једноставно имплементира (помоћу три угнежђена циклуса) и сложеност му је \(O(n^3)\), где је \(n\) број чворова у графу.

Флојд-Варшалов алгоритам можемо употребити и за одређивање транзитивног затворења дате релације (тада нас не занимају дужине пута, већ само постојање пута између два чвора).