4.6Кратчайшиепути

Рассмотриморграфсовзвешеннымидугамиипутьизвершиныiввершинуjвэтомграфе.Суммавесовдугэтогопутиназываетсяегодлиной.Путьминимальнойдлиныизiвjназываетсякратчайшимпутемизiвj.

Дейкстрапредложилследующийалгоритмпостроениякратчайшихпутейизданнойвер-шинывовсеостальныевершиныорграфавслучаенеотрицательныхвесовдуг.

^{РассмотриморграфG=(V,A)свыделеннойвершинойsивесамиw}ij^{,(i,j)∈A.Алго-}

ритмприсваиваетвершинамвременныеипостоянныеметки.Постояннаяметкавершины

равнадлинекратчайшегопутиизsвэтувершину.Крометого,формируетсямассивPred,вкоторомPred(v)содержитномернепосредственногопредшественникавершиныvвкратчайшемпутиизsвv.Такимобразомs,...,Pred(Pred(v)),Pred(v),vявляетсякратчайшимпутемизsвv.

АлгоритмДейкстры(построениякратчайшихпутейизвершиныsвовсеостальныевершиныорграфавслучаенеотрицательныхвесовдуг)

Шаг1.(Начало).ПомечаемвершинуsпостояннойметкойLength(s)=0.Всеосталь-ныевершиныv/=sпомечаютсявременнымиметкамиLength(v)=∞.Полагаемномер

итерацииi=1иномертекущейвершины,помеченнойпостояннойметкой,u=s.

Шаг2.(Рекурсия).Полагаемi=i+1.Рассмотримвершинуu.Длявсехеенепосредствен-ныхпоследователейvсвременнойметкойвычисляемM=min{Length(v),Length(u)+w_uv}.ЕслиMменьшевременнойметкиLength(v),товычисляемновуюметкуLength(v)=

MиполагаемPred(v)=u.

Далеесредивсехвершинсвременнымиметкамивыбираемвершинуkснаименьшеймет-койиделаемеепостоянной.Еслиi<n−1,тополагаемu=kиповторяемШаг2.Иначе

стоп:всекратчайшиепутиизsвостальныевершинымогутбытьвосстановленыпомас-сивуPred.

Алгоритмпостроениякратчайшихпутеймеждувсемипарамивершинипроверкиналичияциклаотрицательноговеса(дополнительныйматериал).ПриводимыйнижеалгоритмпредложенФлойдом.

^{РассмотриморграфG=(V,A).ПустьW0=||w}ij^{||–n×nматрицавесовдугэтогографа.Полагаемw}ij⁼

^{∞,еслидуга(i,j)отсутствует,иw}_ii^{=0длявсехi∈V.АлгоритмФлойдастроитпоследовательность}

ij

матрицW^1,W^2,...,W^nтакую,чтоэлементwⁿ

матрицыW^nравендлинекратчайшегопутиизiвjв

графеG.МатрицаW^{kопределяет}сяпоматрицеW^k−1:

_{wk k−1}

_k−1

_k−1

_ij^=min{w_ij^,w_ik ^+w_kj^{}. (1)}

ij

ПустьP^k–кратчайшийпутьизiвjсвнутреннимивершинамиизмножества{1,2,...,k}.Справедлива

ij

^{Теорема5Для0≤k≤n,величинаwk}

являетсядлинойпутиP^k.

ij

ВалгоритмеФлойдаодновременносдлинамикратчайшихпутейотыскиваютсясамипутиспомощью

ij

_{матрицZ}⁰_,Z¹_,...,Zⁿ_{,гдеэлементz}^k

_{матрицыZ}^k_{указываетнавершину,непосредственноследующую}

ij

заiвP^k.Тогдаясно,что

_z⁰

ij⁼

Ij (j, еслиw0

Ij 0,еслиw0

/=∞,

^=∞.

_{МатрицаZkполучаетсяизZk−1следующимобразом.ПустьM=min{wk−1,wk−1+wk−1}.Тогда}

(_zk−1

_k−1

^ij ik kj

_{zk ij,еслиM=wij,}

_ij=

_zk−1

_k−1

_ik^,еслиM<w_ij^.

_ЕслиM=wk−1_{,тодлинапутиPkравнадлинепутиPk}−1_{.ИначеPkполучаетсяврезультатесклеивания}

ij

_путейPk−1_иPk−1_иzk

ij

_=zk−1_.

ij ^ij

ik kj

^ij ik

^{Очевидно,чтократчайшийпутьизiвjопределяетсяпоследовательностьювершинi,i}₁^,i₂^,...,i_p^,j,где

_i1=zn_,i2=zn

_,i3=zn

_,...,j=zn_.

^{ij i}₁^j

ⁱ₂^j

ⁱ_p^j

_{Отметим,чтов(1)еслиwk−1илиwk−1равно∞,тоwk}

_=wk−1_.

ik kj

^ij ij

АлгоритмФлойда(построениякратчайшихпутеймеждувсемипарамивершинипроверкиналичия

циклаотрицательноговеса)

_{(ВпроцессевычисленийматрицуW}^k_{записываемнаместоW}^k−1_{,аматрицуZ}^k_{–наместоZ}^k−1_,k=

_{1,...,n.Такимобразом,используемодноитожеобозначениеWдлявсехW}^k_{иZдлявсехZ}^k_.)

_{Шаг1.(Начало).Полагаемk=0.СтроимматрицыW=W}⁰_иZ=Z⁰_.

^{Шаг2.(Рекурсия).Полагаемk=k+1.Длявсехтакихвершинi/=k,чтоw}ik^{/=∞ивсехтакихвершин}

^{j/=k,чтоwkj/=∞,вычисляемM=min{wij,wik+wkj}.ЕслиM<wij,тополагаемzij=zikиwij=M.}

^{Еслипоявляетсяw}_ii^{<0,тостоп:вершинаiпринадлежитнекоторомуциклуотрицательноговеса.}

^{Есливсеw}ii^{≥0иk=n,тостоп:w}ij^{–длинывсехкратчайшихпутей,аz}ij^{–перваяпослеiвершинав}

кратчайшемпутиизiвj.

^{Есливсеw}_ii^{≥0иk<n,топовторяемШаг2.}