7-маъруза. Маршрутизация алгоритмларнинг классификацияси ва уларга қўйиладиган талаблар

BIRTH:
11 May 1930, Rotterdam, The Netherlands (Gollandiya)
DEATH:
6 August 2002, Nuenen, The Netherlands.
Эдсгер Вибе Дейкстра машҳур
дастурчи ва назарий физик
Флойд алгоритми - йўналтирилган графнинг барча баландликлари орасидаги энг қисқа масофани топиш учун динамик алгоритм ҳисобланади. У 1962 йилда Роберт Флойд томонидан ишлаб чиқилган, 1959 йилда Бернард Рой (Bernard Roy) худди шу алгоритмни эълон қилган бўлса-да, аммо бу аҳамиятсиз бўлиб қолди.
Бу алгоритм Дейкстри алгоритмига қараганда умумийроқ ҳисобланади, чунки у исталган иккита тармоқ тугунлари орасидаги энг қисқа йўлларни топади. Бу алгоритмда тармоқ n сатрлар ва n устунларга эга бўлган квадрат матрица шаклида берилган. (i, j) элемент i тугундан ј тугунгача бўлган dij масофага тенг, агар (i, j) ёй мавжуд бўлса у чекли қийматга эга ва акс ҳолда чексизликка тенг бўлади.

Эътиборингиз учун рахмат!