Определение
Проблемът с най-краткия път е класически проблем с алгоритъм в изследването на теорията на графите, който има за цел да намери най-краткия път между два възела в график (съставен от възли и пътища). Конкретните форми на алгоритъма включват:
(1) Проблемът с определянето на най-краткия път на началната точка, т.е. проблемът с намирането на най-краткия път, когато началният възел е известен. Подходящо е да се използва алгоритъмът на Дейкстра.
(2) Проблемът с определянето на най-краткия път до крайната точка – противно на проблема с определянето на началната точка, този проблем е проблем с намирането на най-краткия път, когато крайният възел е известен. В неориентирания граф тази задача е напълно еквивалентна на задачата за определяне на началната точка. В насочения граф този проблем е еквивалентен на проблема за определяне на началната точка, в която посоките на всички пътища са обърнати.
(3) Проблемът с определянето на най-краткия път между началната точка и крайната точка - това е, като знаете началната точка и крайната точка, да намерите най-краткия път между два възела.
(4) Глобалният проблем с най-краткия път – намерете всички най-кратки пътища в графиката. Подходящо е да се използва алгоритъмът на Флойд-Уоршал.
Алгоритъм
Дийкстра
Намерете най-краткия път с един източник и без отрицателно тегло. Навременността е добра, а времевата сложност е O(V*V+E). Ако източникът е достъпен, O(V*lgV+E*lgV)=>O(E*lgV).
В случай на редки графики, E=V*V/lgV в този момент, така че времевата сложност на алгоритъма може да бъде O(V^2). Ако стекът на Фибоначи се използва като приоритетна опашка, времевата сложност на алгоритъма е O(V*lgV + E).
Флойд
Намерете най-краткия път с множество източници и ръбове без отрицателно тегло. Използвайте матрица, за да запишете графиката. Навременността е лоша, а времевата сложност е O(V^3).
Алгоритъмът на Флойд-Уоршал (алгоритъм на Флойд-Уоршал) е алгоритъм за решаване на най-краткия път между произволни две точки, който може правилно да се справи с проблема с най-краткия път на насочена графика или отрицателно тегло.
Времевата сложност на алгоритъма на Флойд-Уоршал е O(N^3), а пространствената сложност е O(N^2).
Принципът на Floyd-Warshall е динамично програмиране:
Да предположим, че Di,j,k са от i до j и само възлите в набора (1..k) са междинните възли Дължината на най-краткия път.
Ако най-краткият път минава през точка k, тогава Di,j,k = Di,k,k-1 + Dk,j,k-1;
Ако най-краткият път не минава през точка k, тогава Di,j,k = Di,j,k-1.
Следователно Di,j,k = min(Di,k,k-1 + Dk,j,k-1, Di,j,k-1).
В действителния алгоритъм, за да спестите място, итерирайте директно върху оригиналното пространство, така че пространството да може да бъде намалено до две измерения.
Описанието на алгоритъма на Флойд-Уоршал е както следва:
за k ← 1 до n направи
за i ← 1 до n направи
за j ← 1 до n направи
ако (Di,k + Dk,j < Di,j) тогава
Di,j ← Di,k + Dk,j;< /p>
където Di,j представлява цената от точка i до точка j, когато Di,j е ∞, това означава, че няма връзка между двете точки.
Белман-Форд
За да намерите най-краткия път на един източник, можете да определите дали има цикъл с отрицателно тегло (ако има, няма най-кратък път),
p>Навременността е по-добра, а времевата сложност е O(VE).
Алгоритъмът на Белман-Форд е алгоритъм за решаване на проблема с най-краткия път от един източник.
Проблемът с най-краткия път с една изходна точка се отнася до:
При дадена претеглена насочена графа G и изходна точка s, за всяка точка v в графиката G намерете от s до Най-краткия път на v.
За разлика от алгоритъма на Дейкстра, в алгоритъма на Белман-Форд теглото на ръба може да бъде отрицателно число.
Представете си, че можем да намерим цикъл от графиката (т.е. започвайки от v и връщайки се към v след няколко точки) и сумата от теглата на всички ребра в този цикъл е отрицателна. След това през този цикъл най-краткият път между всеки две точки в цикъла може да бъде безкрайно малък. Ако този отрицателен цикъл не бъде разгледан, програмата ще работи вечно. Алгоритъмът на Белман-Форд има способността да различи този отрицателен цикъл.
SPFA
е оптимизацията на опашката на Bellman-Ford със сравнително добра навременност и времева сложност O(kE). (K<
е подобен на алгоритъма на Белман-Форд. Алгоритъмът SPFA използва поредица от операции за релаксация, за да получи най-краткия път от възел до всички други възли в графиката. Разликата е, че алгоритъмът на SPFA поддържа опашка. Той прави ненужно актуализирането на други възли веднага след актуализирането на текущия най-кратък път на възел, като по този начин значително намалява броя на повтарящите се операции.
SPFA алгоритъмът може да се използва за графики с отрицателни тегла на ръбовете, което е същото като dijkstra. Алгоритъмът е различен.
За разлика от алгоритъма на Дейкстра и алгоритъма на Белман-форд, времевата ефективност на алгоритъма SPFA е нестабилна, т.е. времето, необходимо за различните графики, е много различно.< /p>
В най-добрия случай всеки възел се поставя в опашката само веднъж, тогава алгоритъмът всъщност става обхождане в ширина и времевата му сложност е само O(E). От друга страна, има такива примери, така че всеки възел е поставен в опашка (V-1) пъти. По това време алгоритъмът се изражда до алгоритъма на Белман-форд и времевата му сложност е O(VE).
Алгоритъмът SPFA е в графиката с тегло на отрицателния край. Горното може напълно да замени алгоритъма на Белман-форд и също така се представя добре в разредени графики. Въпреки това, в графика с тегло на неотрицателни ръбове, за да се избегне най-лошият случай, обикновено се използва по-ефективният алгоритъм на Dijkstra и неговата версия за оптимизиране на купчина. Обичайният SPFA алгоритъм не работи задоволително в тип мрежова графика.