Алгоритми за определяне на най-късите разстояния на графика
Интересът към проблема за намиране на най-късите разстояния се обяснява с факта, че този проблем е един от етапите при решаването на повечето проблеми, свързани с товарния транспорт. В същото време в хода на решаването на проблеми, свързани с оптимизацията на товарния трафик, е необходимо многократно да се определят най-кратките разстояния между върховете на графиката. Следователно скоростта на алгоритмите за определяне на най-късите разстояния между върховете на графиката зависи до голяма степен от времето за решаване на целия проблем като цяло.
Нека формулираме проблема с най-краткия път. Нека има дадена свързана графика с R върхове и н ориентирани дъги и на всяка дъга се присвоява неотрицателно число Cij наречена неговата дължина. Необходимо е да се намерят най-кратките пътеки на графиката и техните дължини от даден връх Йо към всички други върхове на тази графика. В този случай дължината на най-краткия път означава сумата от дължините на дъгите, които съставят този път. Всеки връх на графиката може да съдържа само една дъга, принадлежаща към някакъв най-кратък път.
Всички специални алгоритми за решаване на този проблем са итеративни, при които при всяка итерация се увеличава или коригира множеството от най-кратките пътища между върховете на графиката, вече изградени за това.
Повечето от тези алгоритми могат да бъдат класифицирани в две групи.
В алгоритмите на първата група множеството от най-кратки пътища, вече изградени за дадена итерация, остава непроменено, докато при всяка итерация към този набор се добавя по една дъга, т.е. Проблемът е решен за R-един повторение.
В алгоритмите от втората група, конструираният набор от най-кратки пътища може да бъде многократно коригиран при следващи итерации. Именно тези алгоритми са най-ефективни, когато броят на върховете е достатъчно голям.
За да намерите оптималното решение на проблема, можете да използвате методи, които ви позволяват да изчислите най-кратките пътища ръчно или с помощта на компютър.