Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети
Рассматривается алгоритм построения кратчайших путей между всеми парами узлов в неориентированной сети по критерию: минимум дуг в пути; минимум длины пути. Проведен анализ трудоемкости алгоритма и эмпирически показано, что по мере увеличения плотности сети его вычислительная эффективность становится...
Збережено в:
| Дата: | 2014 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/124702 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети / В.А. Васянин // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 122-131. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-124702 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1247022017-10-03T03:02:42Z Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети Васянин, В.А. Системный анализ Рассматривается алгоритм построения кратчайших путей между всеми парами узлов в неориентированной сети по критерию: минимум дуг в пути; минимум длины пути. Проведен анализ трудоемкости алгоритма и эмпирически показано, что по мере увеличения плотности сети его вычислительная эффективность становится выше, чем у алгоритма Флойда, соответствующим образом модифицированного для нахождения кратчайших путей по ступенчатому критерию. Розглянуто алгоритм побудови найкоротших шляхів між усіма парами вузлів у неорієнтованій мережі за критерієм: мінімум дуг у шляху; мінімум довжини шляху. Проведено аналіз складності алгоритму та емпірично показано, що в міру зростання щільності мережі його обчислювальна ефективність стає на кілька порядків вищою, ніж у алгоритму Флойда, відповідно модифікованого для відшукання найкоротших шляхів за ступінчатим критерієм. The algorithm of finding all shortest paths in undirected network is considered. Two criteria are used: the minimum number of arcs in the path and minimum path length. The algorithm is analyzed for complexity and it is empirically shown that as the network density increases, the computational efficiency of the proposed algorithm becomes higher than that of the Floyd algorithm adequately modified to find the shortest path by two criteria. 2014 Article Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети / В.А. Васянин // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 122-131. — Бібліогр.: 12 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/124702 519.168 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Васянин, В.А. Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети Кибернетика и системный анализ |
| description |
Рассматривается алгоритм построения кратчайших путей между всеми парами узлов в неориентированной сети по критерию: минимум дуг в пути; минимум длины пути. Проведен анализ трудоемкости алгоритма и эмпирически показано, что по мере увеличения плотности сети его вычислительная эффективность становится выше, чем у алгоритма Флойда, соответствующим образом модифицированного для нахождения кратчайших путей по ступенчатому критерию. |
| format |
Article |
| author |
Васянин, В.А. |
| author_facet |
Васянин, В.А. |
| author_sort |
Васянин, В.А. |
| title |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_short |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_full |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_fullStr |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_full_unstemmed |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| title_sort |
двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2014 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/124702 |
| citation_txt |
Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети / В.А. Васянин // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 122-131. — Бібліогр.: 12 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT vasâninva dvuhkriterialʹnyjleksikografičeskijalgoritmpostroeniâvsehkratčajšihputejvseti |
| first_indexed |
2025-07-09T01:53:52Z |
| last_indexed |
2025-07-09T01:53:52Z |
| _version_ |
1837132450091761664 |
| fulltext |
ÓÄÊ 519.168
Â.À. ÂÀÑßÍÈÍ
ÄÂÓÕÊÐÈÒÅÐÈÀËÜÍÛÉ ËÅÊÑÈÊÎÃÐÀÔÈ×ÅÑÊÈÉ ÀËÃÎÐÈÒÌ
ÏÎÑÒÐÎÅÍÈß ÂÑÅÕ ÊÐÀÒ×ÀÉØÈÕ ÏÓÒÅÉ Â ÑÅÒÈ
Àííîòàöèÿ. Ðàññìàòðèâàåòñÿ àëãîðèòì ïîñòðîåíèÿ êðàò÷àéøèõ ïóòåé ìåæäó âñåìè ïàðà-
ìè óçëîâ â íåîðèåíòèðîâàííîé ñåòè ïî êðèòåðèþ: ìèíèìóì äóã â ïóòè; ìèíèìóì äëèíû
ïóòè. Ïðîâåäåí àíàëèç òðóäîåìêîñòè àëãîðèòìà è ýìïèðè÷åñêè ïîêàçàíî, ÷òî ïî ìåðå
óâåëè÷åíèÿ ïëîòíîñòè ñåòè åãî âû÷èñëèòåëüíàÿ ýôôåêòèâíîñòü ñòàíîâèòñÿ âûøå, ÷åì
ó àëãîðèòìà Ôëîéäà, ñîîòâåòñòâóþùèì îáðàçîì ìîäèôèöèðîâàííîãî äëÿ íàõîæäåíèÿ
êðàò÷àéøèõ ïóòåé ïî ñòóïåí÷àòîìó êðèòåðèþ.
Êëþ÷åâûå ñëîâà: ìíîãîêðèòåðèàëüíûå çàäà÷è ïîñòðîåíèÿ êðàò÷àéøèõ ïóòåé, àëãîðèòìû,
âû÷èñëèòåëüíàÿ òðóäîåìêîñòü.
ÂÂÅÄÅÍÈÅ
Âî ìíîãèõ òåîðåòè÷åñêèõ è ïðèêëàäíûõ çàäà÷àõ îïòèìèçàöèè íà ãðàôàõ, òà-
êèõ, íàïðèìåð, êàê ïðîåêòèðîâàíèå òðàíñïîðòíûõ, èíôîðìàöèîííûõ è òåëå-
êîììóíèêàöèîííûõ ñåòåé, òðåáóåòñÿ ïîñòðîåíèå êðàò÷àéøèõ ïóòåé (ÊÏ).
 áîëüøåé ÷àñòè ïóáëèêàöèé, ïîñâÿùåííûõ âîïðîñàì íàõîæäåíèÿ ÊÏ, ðàñ-
ñìàòðèâàþòñÿ çàäà÷è ïîñòðîåíèÿ ÊÏ ïî îäíîìó êðèòåðèþ — ìèíèìóì èëè
ìàêñèìóì ñóììû äëèí äóã â ïóòè. Ïîä äëèíîé äóãè ïîíèìàåòñÿ íåêîòîðûé åå
ïàðàìåòð, íàïðèìåð ðàññòîÿíèå ïî äóãå, çàòðàòû ïðè ïåðåâîçêå ïî äóãå, ïðî-
ïóñêíàÿ ñïîñîáíîñòü äóãè è ò.ï.
Íàðÿäó ñ çàäà÷àìè ïîñòðîåíèÿ ÊÏ ïî îäíîìó êðèòåðèþ çíà÷èòåëüíûé èíòå-
ðåñ ïðåäñòàâëÿþò ìíîãîêðèòåðèàëüíûå çàäà÷è î ïóòÿõ (ÌÊÏ), åñòåñòâåííûì îáðà-
çîì âîçíèêàþùèå âî ìíîãèõ ïðèëîæåíèÿõ, êîãäà èìååòñÿ íåñêîëüêî ðàçëè÷íûõ
ïàðàìåòðîâ, õàðàêòåðèçóþùèõ óçëû è äóãè ñåòè.  áîëüøèíñòâå ñëó÷àåâ âûáîð
îïòèìàëüíûõ êðàò÷àéøèõ ïóòåé ïî ýêñòðåìàëüíûì çíà÷åíèÿì ýòèõ ïàðàìåòðîâ
ïðåäñòàâëÿåò ñëîæíóþ çàäà÷ó, ïîñêîëüêó ïàðàìåòðû ìîãóò áûòü ïðîòèâîðå÷èâû-
ìè è êîíêóðèðîâàòü ìåæäó ñîáîé. Êîíöåïöèÿ îïòèìèçàöèè ÌÊÏ çàäà÷è â öåëîì,
â îòëè÷èå îò çàäà÷è îïòèìèçàöèè ïóòåé ïî îäíîìó êðèòåðèþ, çàêëþ÷àåòñÿ â íåîá-
õîäèìîñòè íàõîæäåíèÿ íåêîòîðîãî îïòèìàëüíîãî ðåøåíèÿ ïî âñåì çàäàííûì êðè-
òåðèÿì.  ýòîì ñëó÷àå, êàê ïðàâèëî, ñóùåñòâóåò íå îäíî, à ìíîæåñòâî ïàðå-
òî-îïòèìàëüíûõ ðåøåíèé çàäà÷è, óäîâëåòâîðÿþùèõ âñåì êðèòåðèÿì.
Ïîñêîëüêó îáçîð ñîâðåìåííûõ ìíîãîêðèòåðèàëüíûõ àëãîðèòìîâ ïðåäñòàâëÿåò
îòäåëüíóþ òåìó, âûõîäÿùóþ çà ðàìêè íàñòîÿùåé ñòàòüè, îòìåòèì ëèøü, ÷òî îíè
èññëåäîâàëèñü ìåíåå äîñêîíàëüíî, íàïðèìåð ðàáîòà Õàíñåíà [1], îïóáëèêîâàííàÿ
â 1979 ã. è ïîñâÿùåííàÿ ñèñòåìàòè÷åñêîìó èññëåäîâàíèþ äâóõêðèòåðèàëüíûõ çà-
äà÷ î ïóòÿõ. Õàíñåí [1] è íåçàâèñèìî Âàðáàðòîí [2] ðàçðàáîòàëè ïîëíîñòüþ ïîëè-
íîìèàëüíóþ ñõåìó ðåøåíèÿ ÌÊÏ çàäà÷è (fully polynomial time approximation
schemes — FPTAS) äëÿ ïàðåòî-îïòèìàëüíûõ ðåøåíèé â ñëó÷àå äâóõ êðèòåðèåâ.
Äâóõêðèòåðèàëüíûå çàäà÷è òàêæå áûëè äîñòàòî÷íî èññëåäîâàíû â [3]. Ïîñëå
ýòèõ ïóáëèêàöèé ïîÿâèëîñü äîñòàòî÷íî ìíîãî ðàáîò, ñâÿçàííûõ ñ ìíîãîêðèòåðè-
àëüíûìè çàäà÷àìè î ÊÏ, â êîòîðûõ èññëåäîâàëèñü âîïðîñû ðàçðàáîòêè ýôôåê-
òèâíûõ àëãîðèòìîâ íàõîæäåíèÿ ïàðåòî-îïòèìàëüíûõ ïóòåé ïî íåñêîëüêèì êîí-
êóðèðóþùèì ìåæäó ñîáîé êðèòåðèÿì. Äëÿ ñëó÷àåâ, êîãäà ÷èñëî êðèòåðèåâ îïòè-
ìèçàöèè áîëüøå äâóõ, ïîêà íå äîñòèãíóòî îñîáûõ ðåçóëüòàòîâ. Ñóäÿ ïî
ëèòåðàòóðíûì èñòî÷íèêàì è ïóáëèêàöèÿì â Èíòåðíåòå, îñîáûõ ïðîäâèæåíèé
â ðåøåíèè ÌÊÏ çàäà÷ ñ èñïîëüçîâàíèåì FPTAS-ñõåì ïîêà íå íàáëþäàåòñÿ.
122 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5
© Â.À. Âàñÿíèí, 2014
 íàñòîÿùåé ñòàòüå ðàññìàòðèâàþòñÿ àëãîðèòìû ïîñòðîåíèÿ ÊÏ, óïîðÿäî÷åí-
íûõ â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå ïî äâóì êðèòåðèÿì. Èçâåñòíî, ÷òî òàêèå àëãî-
ðèòìû èìåþò ïîëèíîìèàëüíóþ òðóäîåìêîñòü â îòëè÷èå îò àëãîðèòìîâ íàõîæäå-
íèÿ ïàðåòî-îïòèìàëüíûõ êðàò÷àéøèõ ïóòåé. Íåêîòîðûå àëãîðèòìû ïîñòðîåíèÿ
ñòóïåí÷àòûõ äâóõêðèòåðèàëüíûõ ïóòåé ðàññìàòðèâàëèñü â ðàáîòàõ [4, 5]. Èäåÿ
àëãîðèòìà, ïðåäëîæåííîãî â [4], áëèçêà ê èäåå àëãîðèòìà Ìóðà [6] è îòëè÷àåòñÿ
îñîáåííîñòüþ ðåàëèçàöèè ïðîöåäóðû ðàññòàíîâêè «ïîìåòîê» ñ ïîìîùüþ ëîãè-
÷åñêèõ îïåðàöèé íàä ñòðîêàìè ìàòðèö, õàðàêòåðèçóþùèõ ñåòü. Êàê ïîêàçàíî
â [7], àñèìïòîòè÷åñêàÿ òðóäîåìêîñòü àëãîðèòìîâ òàêîãî òèïà ñîñòàâëÿåò O n( )3 ,
ãäå n — ÷èñëî óçëîâ â ñåòè.  ðàáîòå [5] èçëîæåí àëãîðèòì, ñòðîÿùèé äåðåâüÿ
êðàò÷àéøèõ ïóòåé ïî äâóõñòóïåí÷àòîìó êðèòåðèþ: ìèíèìóì ðàíãà ïóòè, ïðè ðà-
âåíñòâå ðàíãîâ — ìàêñèìóì ïðîïóñêíîé ñïîñîáíîñòè (ïîä ðàíãîì ïóòè ïîíèìà-
åòñÿ ÷èñëî òðàíçèòíûõ óçëîâ èëè äóã â ïóòè). Ñóòü àëãîðèòìà çàêëþ÷àåòñÿ â ñëå-
äóþùåì: îò íåêîòîðîãî óçëà i íåîáõîäèìî ïîñòðîèòü äåðåâî ÊÏ äî âñåõ îñòàëü-
íûõ óçëîâ. Ïîñêîëüêó ïóòè ñ ðàíãîì 1 óæå ïîñòðîåíû, íà ïåðâîé èòåðàöèè
àëãîðèòìà ñòðîÿòñÿ ïóòè ñ ðàíãîì 2. Íà êàæäîé ïîñëåäóþùåé èòåðàöèè ñòðîÿòñÿ
ïóòè ñ ðàíãîì, áîëüøèì íà åäèíèöó ïðåäøåñòâóþùåãî ðàíãà. Èòåðàöèÿ âêëþ÷à-
åò äâà âëîæåííûõ öèêëà ïî ÷èñëó óçëîâ â ñåòè, ïîýòîìó àñèìïòîòè÷åñêàÿ òðóäî-
åìêîñòü èòåðàöèè ñîñòàâëÿåò O n( )2 . Äëÿ ïîñòðîåíèÿ äåðåâà ÊÏ îò óçëà i ïîòðå-
áóåòñÿ O q ni(( ) )�1 2 äåéñòâèé, ãäå qi — ìàêñèìàëüíûé ðàíã ÊÏ, ïîñòðîåííîãî îò
óçëà i. Íàõîæäåíèå äåðåâüåâ ÊÏ îò âñåõ óçëîâ ïîòðåáóåò ñëîæíîñòè ïîðÿäêà
O q n(( ) )max �1 3 â ïðåäïîëîæåíèè, ÷òî äëÿ âñåõ óçëîâ èìååì q qi � max .
Ñëåäóåò îñîáî îòìåòèòü, ÷òî äëÿ ïîñòðîåíèÿ ïóòåé ïî ñòóïåí÷àòîìó êðèòå-
ðèþ ëåãêî ìîäèôèöèðîâàòü ëþáîé èçâåñòíûé àëãîðèòì ïîñòðîåíèÿ ÊÏ ïî îäíî-
ìó êðèòåðèþ, íàïðèìåð àëãîðèòì Ôëîéäà [8] èëè Äåéêñòðû [9]. Êàê èçâåñòíî,
ýòè àëãîðèòìû èìåþò àñèìïòîòè÷åñêóþ òðóäîåìêîñòü ïîðÿäêà O n( )3 äëÿ
ïîñòðîåíèÿ ÊÏ îò âñåõ óçëîâ.
Êàê ïðàâèëî, ïðè ðåøåíèè áîëüøèíñòâà ïðàêòè÷åñêèõ çàäà÷ íàõîæäåíèÿ ÊÏ
ïî äâóì êðèòåðèÿì íàèáîëüøèé èíòåðåñ ïðåäñòàâëÿþò àëãîðèòìû, èñïîëüçóþ-
ùèå â êà÷åñòâå êðèòåðèåâ îïòèìèçàöèè ìèíèìóì òðàíçèòíûõ óçëîâ èëè äóã
â ïóòè (ðàíã ïóòè) è ìèíèìóì äëèíû ïóòè. Â ñâÿçè ñ ýòèì â íàñòîÿùåé ðàáîòå
ðåêîìåäóåòñÿ óëó÷øåííàÿ âåðñèÿ äâóõêðèòåðèàëüíîãî àëãîðèòìà ïîñòðîåíèÿ
âñåõ ÊÏ â ñåòè ïî óêàçàííûì êðèòåðèÿì, ïðåäëîæåííîãî â ðàáîòå [10]. Ïîñêîëü-
êó â íàñòîÿùåé ñòàòüå ðàññìàòðèâàåòñÿ ïîñòðîåíèå ÊÏ îò âñåõ óçëîâ â ñåòè, òðó-
äîåìêîñòü ïðåäëîæåííîãî àëãîðèòìà áóäåò ñðàâíèâàòüñÿ ñ òðóäîåìêîñòüþ èçìå-
íåííîãî ïî òàêèì æå êðèòåðèÿì àëãîðèòìà Ôëîéäà. Ñëåäóåò îòìåòèòü, ÷òî
ïðèâåäåííûå àëãîðèòìû ìîãóò áûòü ëåãêî îáîáùåíû è íà ñëó÷àé íàëè÷èÿ
áîëüøåãî ÷èñëà óïîðÿäî÷åííûõ êðèòåðèåâ îïòèìèçàöèè.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È È ÀËÃÎÐÈÒÌ ÐÅØÅÍÈß
Ïóñòü çàäàíà ïðîñòàÿ íåîðèåíòèðîâàííàÿ ñåòü G N P( , ) ñ ìíîæåñòâîì óçëîâ N ,
n N� | | , è ìíîæåñòâîì äóã P, p P� | |. Êàæäîé äóãå p Pkl � ïîñòàâëåíî â ñîîò-
âåòñòâèå íåêîòîðîå ÷èñëî rkl � 0, óñëîâíî íàçûâàåìîå åå äëèíîé. Íàçîâåì ÷èñ-
ëî äóã, ñîñòàâëÿþùèõ íåêîòîðûé ïóòü, ðàíãîì ïóòè. Òðåáóåòñÿ ïîñòðîèòü ÊÏ
ìåæäó âñåìè óçëàìè ñåòè, óäîâëåòâîðÿþùèå êðèòåðèþ: ìèíèìóì ðàíãà ïóòè,
ïðè ðàâåíñòâå ðàíãîâ — ìèíèìóì äëèíû.
Èäåÿ ïðåäëàãàåìîãî àëãîðèòìà ñõîäíà ñ èäååé àëãîðèòìà Áåëëìàíà–Øèìáå-
ëà [11, 12], ñîãëàñíî êîòîðîé íà êàæäîé óñëîâíîé l-é èòåðàöèè ñòðîÿòñÿ âñå ÊÏ
â ñåòè ñ ðàíãîì äî 2 l âêëþ÷èòåëüíî. Ïðè ýòîì íà êàæäîé ïîñëåäóþùåé èòåðàöèè
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5 123
èñïîëüçóþòñÿ âñå ïóòè, ïîñòðîåííûå íà ïðåäûäóùèõ, è ïðèìåíÿåòñÿ ýôôåêòèâ-
íàÿ òåõíèêà ïðåäñòàâëåíèÿ àáñòðàêòíûõ òèïîâ äàííûõ (ÀÒÄ).
Ïóñòü R rij n n� �|| || — òîïîëîãè÷åñêàÿ ìàòðèöà; rij — äëèíà äóãè pij (åñëè
äóãè pij íå ñóùåñòâóåò, rij � �); D dij n n� �|| || — ìàòðèöà äëèí ïîñòðîåííûõ ïó-
òåé; C cij n n� �|| || — ñïðàâî÷íàÿ ìàòðèöà ïîñòðîåííûõ ïóòåé, êàæäûé ýëåìåíò
êîòîðîé cij , i j� , îïðåäåëÿåò íîìåð ïðåäïîñëåäíåãî óçëà íà êðàò÷àéøåì ïóòè îò i
äî j‚ cii � 0, i n�1, ; Q qij n n� �|| || — ìàòðèöà ðàíãîâ ïîñòðîåííûõ ïóòåé. Ïåðâî-
íà÷àëüíî D ñîâïàäàåò ñ R, à äëÿ ïóòåé ñ ðàíãîì 1 ñîîòâåòñòâóþùèå ýëåìåíòû
ìàòðèö qij �1, c iij � . Äëÿ íåíàéäåííûõ ïóòåé èìååì qij � � , cij � 0. Çíàêè ,
è � ñîîòâåòñòâåííî îçíà÷àþò îïåðàöèè ïðèñâàèâàíèÿ, êîíúþíêöèè (ëîãè÷åñêî-
ãî «è») è äèçúþíêöèè (ëîãè÷åñêîãî «èëè»). Çíàêîì *** îòäåëÿþòñÿ êîììåíòàðèè.
Ïðèâåäåì àëãîðèòì ïîñòðîåíèÿ ÊÏ ïî ñòóïåí÷àòîìó êðèòåðèþ [10].
Àëãîðèòì SP1
1. RMAX 1; l 0.
2. KU 0; l l �1.
3. Äëÿ {i i n| , }�1 âûïîëíèòü ïï. 4–16.
4. KS 0.
5. Äëÿ { j j n| , }�1 âûïîëíèòü ïï. 6–14.
6. Åñëè ( )i j cij�
� 0, òî ïåðåéòè ê ï. 7; èíà÷å âûïîëíèòü KS KS �1 è ïå-
ðåéòè ê ï. 14.
7. Äëÿ {k k n| , }�1 âûïîëíèòü ïï. 8–12.
8. Åñëè Q i k RMAX Q k j RMAX( , ) ( , )
, òî ïåðåéòè ê ï. 9; èíà÷å ïå-
ðåéòè ê ï. 12.
9. RT Q i k Q k j �( , ) ( , ) .
10. Åñëè RT Q i j RT Q i j D i j D i k D k j� � �
� �( , ) ( ( , ) ( , ) ( , ) ( , )) , òî ïåðåéòè
ê ï. 11; èíà÷å ïåðåéòè ê ï. 12.
11. D i j D i k D k j( , ) ( , ) ( , ) � ; Q i j RT( , ) ; C i j C k j( , ) ( , ) .
12. Ïåðåéòè ê ï. 7. *** Êîíåö öèêëà ïî k
13. Åñëè C i j( , ) � 0 , òî KS KS �1.
14. Ïåðåéòè ê ï. 5. *** Êîíåö öèêëà ïî j
15. Åñëè KS n� , òî KU KU �1.
16. Ïåðåéòè ê ï. 3. *** Êîíåö öèêëà ïî i
17. RMAX RMAX 2 .
18. Åñëè RMAX n KU n
�( – )1 , òî ïåðåéòè ê ï. 2, èíà÷å ê ï. 19.
19. Åñëè RMAX n KU n�
�( – )1 , òî âûâåñòè ñîîáùåíèå î íåñâÿçíîñòè ñåòè.
20. Êîíåö.
Ïðèâåäåì èçìåíåííûé àëãîðèòì Ôëîéäà äëÿ ïîñòðîåíèÿ ÊÏ ïî ñòóïåí÷àòî-
ìó êðèòåðèþ.
Àëãîðèòì Floyd
1. Äëÿ {i i n| , }�1 âûïîëíèòü ïï. 2–9.
2. Äëÿ { j j n| , }�1 , åñëè i j� , âûïîëíèòü ïï. 3–8.
3. Äëÿ {k k n| , }�1 , åñëè k j i� � , âûïîëíèòü ïï. 4–7.
4. Åñëè Q j i Q i k( , ) ( , )� �
� �, òî ïåðåéòè ê ï. 5; èíà÷å ïåðåéòè ê ï. 7.
5. Åñëè ( ( , ) ( , ) ( , )) ( ( , ) ( , ) ( , ) ( ,Q j k Q j i Q i k Q j k Q j i Q i k D j k� � � � �
) ( , )� �D j i
� D i k( , )) , òî ïåðåéòè ê ï. 6; èíà÷å ïåðåéòè ê ï. 7.
6. Q j k Q j i Q i k( , ) ( , ) ( , ) � ; D j k D j i D i k( , ) ( , ) ( , ) � ; C j k C i k( , ) ( , ) .
7. Ïåðåéòè ê ï. 3.
8. Ïåðåéòè ê ï. 2.
124 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5
9. Ïåðåéòè ê ï. 1.
10. Êîíåö.
 àëãîðèòìå SP1 â ñòðîêå 2 íà÷èíàåòñÿ öèêë, ïðåäñòàâëÿþùèé óñëîâíûå
èòåðàöèè, îáùåå ÷èñëî êîòîðûõ äëÿ ïîñòðîåíèÿ âñåõ ïóòåé â ñåòè íàêàïëèâàåòñÿ
â l . Óñëîâíàÿ èòåðàöèÿ ñîäåðæèò òðè âëîæåííûõ öèêëà ïî èíäåêñàì: i, j‚ k.
Ïðåäïîëîæèì, ÷òî êàæäîìó íîìåðó l , l � 0 1 2, , ,�, óñëîâíîé èòåðàöèè àëãî-
ðèòìà SP1 ïîñòàâëåíî âî âçàèìíî-îäíîçíà÷íîå ñîîòâåòñòâèå ìíîæåñòâî
{ }1 2 2 1� �l l, ..., ðàíãîâ ïóòåé. Íàçîâåì ýòî ñîîòâåòñòâèå òàáëèöåé ðàíãîâ. Êîð-
ðåêòíîñòü àëãîðèòìà ñëåäóåò èç äîêàçàííûõ â [10] ñëåäóþùèõ óòâåðæäåíèé.
Ëåììà. Ïóñòü â àëãîðèòìå SP1 íà l-é èòåðàöèè äîïóñêàåòñÿ ïîñòðîåíèå ïó-
òåé ñ ðàíãîì, áîëüøèì 2 l , òîãäà êðàò÷àéøèå ïóòè áóäóò ïîñòðîåíû íåêîððåêòíî.
Äîêàçàòåëüñòâî. Â ñòðîêå 8 àëãîðèòìà SP1 âî âíóòðåííåì öèêëå ïî k âîç-
ìîæíî Q i k( , )� � è Q k j( , )� � . Ïóñòü íà íåêîòîðîé l-é èòåðàöèè ïîñòðîåíû ïóòè
( , )i k1 , ( , )i k2 , ïðè÷åì 2 2 1 1 2
l Q i k Q i k Q k k� � � � �( , ) ( , ) ( , ) è íîìåð k2 áîëüøå íî-
ìåðà k1. Ïîñêîëüêó â öèêëå ïî k îñóùåñòâëÿåòñÿ ïåðåáîð âñåõ íîìåðîâ óçëîâ
â âîçðàñòàþùåì ïîðÿäêå, òî íàéäåòñÿ óçåë ñ íîìåðîì k k k3 2 1� � òàêîé, ÷òî
Q i k Q i k Q k k
D i k D i k D k k
( , ) ( , ) ( , ),
( , ) ( , ) ( , )
2 3 3 2
2 3 3 2
� �
� � � D i k D i k D k k( , ) ( , ) ( , ).2 1 1 2� �
(1)
Îäíàêî ê ìîìåíòó îïðåäåëåíèÿ ïóòè äî k2 èìååì Q i k( , )3 � � èëè
Q k k( , )3 2 � �, ò.å. ïóòü ( , )i k3 èëè ( , )k k3 2 åùå íå íàéäåí. Íà l-é èòåðàöèè
ïóòü ( , )i k2 ïîëó÷èë îòìåòêó C i k k( , )2 1� è íà ïîñëåäóþùèõ èòåðàöèÿõ ðàñ-
ñìàòðèâàòüñÿ íå áóäåò; â ñèëó âûïîëíåíèÿ (1) ýòîò ïóòü íåêîððåêòåí.
Òåîðåìà 1. Íà êàæäîé óñëîâíîé èòåðàöèè àëãîðèòìà SP1 ñòðîÿòñÿ âñå êðàò-
÷àéøèå ïóòè â ñåòè, ñîîòâåòñòâóþùèå òàáëèöå ðàíãîâ.
Äîêàçàòåëüñòâî. Ïîñêîëüêó íà êàæäîé l-é èòåðàöèè àëãîðèòìà íåëüçÿ ñòðîèòü
ïóòè ñ ðàíãîì, áîëüøèì 2 l (ëåììà), äëÿ ïîñòðîåíèÿ ïóòåé íà ýòîé èòåðàöèè èñïîëü-
çóåì òîëüêî òå ïóòè, êîòîðûå ïîñòðîåíû íà ( )l �1 -é èòåðàöèè. Ôàêòè÷åñêè ýòî ãà-
ðàíòèðóåòñÿ èñïîëüçîâàíèåì â öèêëå ïî k â ñòðîêå 8 ñëåäóþùèõ îïåðàöèé ñðàâíå-
íèÿ: Q i k RMAX( , )
, Q k j RMAX( , )
, RMAX l� 2 , l � �0 1, , , à ïåðâîé óñëîâíîé
èòåðàöèè ñîîòâåòñòâóåò íîìåð l � 0. Î÷åâèäíî, ÷òî íà êàæäîé l-é èòåðàöèè àëãîðèò-
ìà áóäóò ïîñòðîåíû âñå ïóòè â ñåòè ñ ðàíãàìè, ñòðîãî ñîîòâåòñòâóþùèìè òàáëèöå
ðàíãîâ. Äîêàæåì, ÷òî ïîñòðîåííûå ïóòè ÿâëÿþòñÿ êðàò÷àéøèìè. Ïóñòü íà m-é èòå-
ðàöèè ïîëó÷åí ïóòü ( , )i j , íå óäîâëåòâîðÿþùèé êðèòåðèþ: ìèíèìóì ðàíãà, ìèíè-
ìóì äëèíû. Çíà÷èò, ñóùåñòâóåò äðóãîé êðàò÷àéøèé ïóòü, êîòîðûé ïðîõîäèò ÷åðåç
óçåë u, ïðè÷åì ëèáî Q i u( , ) , ëèáî Q u j( , ) íå îïðåäåëåíû. Ïîñêîëüêó íà m-é èòåðà-
öèè èñïîëüçóþòñÿ âñå ïóòè, ïîñòðîåííûå íà ( )m �1 -é èòåðàöèè, âî âíóòðåííåì öèê-
ëå ïî k âûïîëíÿåòñÿ èñ÷åðïûâàþùèé ïîèñê ïóòåé ìåæäó i è j ñðåäè âñåõ ïóòåé ñ
ìíîæåñòâîì ðàíãîâ { }1 2 2 1� �m m, ..., ïî ñòóïåí÷àòîìó êðèòåðèþ:
t Q i k Q k j k n k u� � � �arg { }min ( , ) ( , ) , , , ;1
D i j D i D j t( , ) min ( , ) ( , ) ,� � �{ }� � � ,
ãäå t — ìíîæåñòâî óçëîâ, ÷åðåç êîòîðûå ïóòè èìåþò îäèíàêîâûé ðàíã. Ñëå-
äîâàòåëüíî, ïóòü ( , )i j ÷åðåç óçåë u ìîã áûòü ïîñòðîåí òîëüêî íà ïîñëåäóþùèõ
èòåðàöèÿõ è èìåë áû áîëüøèé ðàíã, ÷òî ïðîòèâîðå÷èò ïðåäïîëîæåíèþ î ñó-
ùåñòâîâàíèè äðóãîãî êðàò÷àéøåãî ïóòè. Òåîðåìà äîêàçàíà.
Ñëåäñòâèå. Äëÿ ïîñòðîåíèÿ îïòèìàëüíîãî ïóòè ñ ðàíãîì m (m � 2) òðåáóåòñÿ
� �log 2 m óñëîâíûõ èòåðàöèé àëãîðèòìà SP1, ãäå ñèìâîë � �� îçíà÷àåò îêðóãëåíèå
÷èñëà äî áîëüøåãî öåëîãî.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5 125
Ïóñòü S m�� �log 2 , ãäå m — ìàêñèìàëüíûé ðàíã ïóòè ñðåäè âñåõ êðàò÷àé-
øèõ ïóòåé, ïîñòðîåííûõ â ñåòè.
Òåîðåìà 2. Âðåìÿ, íåîáõîäèìîå àëãîðèòìó SP1 äëÿ ïîñòðîåíèÿ âñåõ êðàò-
÷àéøèõ ïóòåé â ñåòè, âîçðàñòàåò ïðîïîðöèîíàëüíî ôóíêöèè Sn n S c3 2 3� � �( )
� �2n S c( ) , ãäå c — íåêîòîðàÿ êîíñòàíòà.
Îöåíèì òðóäîåìêîñòü àëãîðèòìà SP1. Îáîçíà÷èì hk i, êîëè÷åñòâî ïóòåé, ïî-
ñòðîåííûõ îò óçëà i è èìåþùèõ ðàíã k. Òîãäà äëÿ ïîñòðîåíèÿ âñåõ êðàò÷àéøèõ
ïóòåé â ñåòè ÷èñëî âûõîäîâ àëãîðèòìà íà âíóòðåííèé öèêë ïî k îïðåäåëèòñÿ
ñëåäóþùèì îáðàçîì:
n h n h h ni
i
n
i
n
i i
i
n
� � � � � � � � �
� � �
� � �( ) ( ( )) ( (, , ,1 11
1 1
1 2
1
� 1 1 2 3 2
1� � � � � ��h h h hi i i S
i
, , , ( )
,
))�
� � � � � � � � � � � �
�
� ( ( ) ( ) (, , , , ,n h n h h n h hi
i
n
i i i i1 1 11
1
1 2 1 2� � � � ��h hi S
i3 2
1, ( )
,
))�
� � � � � � � � � �
�
� ( ( ( ) ( ) ( ), , , ,nS S h S h S h S h Si
i
n
i i i1
1
2 3 41 2 2 � � ��h S
i2
1( )
,
))
� � � �
�
�
�
� �
�
� �
� �
�
( ) ( ) ,
, ...,
( )
nS S S l h
l
S
k i
k
l l0
1
1 2 2
1
{ }� �
�
�
�
�
�
�
�
i
n
1
� � � �
� �
�
� �
� �
�
Sn n S l h
i
n
l
S
k i
k
l l
( ) ( ) ,
, ...,
( )
1
1 0
1
1 2 2
1
{� � }
� ,
ãäå ñèìâîë � �� îçíà÷àåò îêðóãëåíèå ÷èñëà äî ìåíüøåãî öåëîãî.
×èñëî âûïîëíåíèé öèêëà ïî k çàâèñèò îò ñòðóêòóðû èñõîäíîé ñåòè, è ñ óâå-
ëè÷åíèåì ÷èñëà óñëîâíûõ èòåðàöèé àëãîðèòìà ïî l ñòðåìèòñÿ ê ( )n �2 . Ïîýòîìó
äàäèì îöåíêó ñâåðõó òðóäîåìêîñòè àëãîðèòìà â õóäøåì ñëó÷àå:
T Sn n n n S l h
i
n
k i
k
l
òp
{
� � � � � �
� � �
�
�
( )( ) ( ) ( ) ,
,
( )
1 2 2
1 1 2
1� � ..., 20
1
ll
S
}
��
�
�
. (2)
Îáîçíà÷èì ( ) ,
,...,
( )
S l h ck i
kl
S
l l
� �
� ��
�
�
��
{ }� �1 2 20
1
1
â ïðåäïîëîæåíèè, ÷òî h hk i k, �
äëÿ âñåõ i N� , òîãäà (2) ïåðåïèøåì â âèäå
T Sn n n n c Sn n S c n S c
i
n
òp � � � � � � � � � �
�
�( )( ) ( ) ( ) ( )1 2 2 3 2
1
3 2 . (3)
Òåîðåìà äîêàçàíà.
Ïîñêîëüêó àñèìïòîòè÷åñêàÿ òðóäîåìêîñòü àëãîðèòìà Ôëîéäà ñîñòàâëÿåò
âñåãäà O n( )3 , ìîæíî ïðåäïîëàãàòü, ÷òî ïðè óâåëè÷åíèè ïëîòíîñòè ãðàôà èëè ñåòè
áûñòðîäåéñòâèå àëãîðèòìà SP1 áóäåò óâåëè÷èâàòüñÿ â îòëè÷èå îò áûñòðîäåé-
ñòâèÿ àëãîðèòìà Ôëîéäà.
Èç àíàëèçà àëãîðèòìà SP1 âèäíî, ÷òî åãî òðóäîåìêîñòü ìîæíî óìåíüøèòü
çà ñ÷åò ñîêðàùåíèÿ ïåðåáîðà óçëîâ j â öèêëå â ñòðîêå 5 ïðè âûáîðå óçëîâ, ïóòè
ê êîòîðûì åùå íå íàéäåíû, è óçëîâ k â öèêëå â ñòðîêå 7 ïðè âûáîðå óçëîâ, ïóòè
ê êîòîðûì óæå íàéäåíû. Ââåäåì ñëåäóþùèå ñòðóêòóðû äàííûõ. Ïóñòü
A aij n n� � �|| || ( )1 — ìàòðèöà, ñîäåðæàùàÿ íîìåðà óçëîâ, ïóòè ê êîòîðûì íàéäå-
íû. Ïðè ýòîì â ïåðâîé ñòðîêå ìàòðèöû íàõîäÿòñÿ íîìåðà óçëîâ, ê êîòîðûì íàé-
126 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5
äåíû ïóòè îò ïåðâîãî óçëà, âî âòîðîé ñòðîêå — îò âòîðîãî óçëà è ò.ä. Ââåäåì
òàêæå âåêòîð T ti n� || || , ãäå íàêàïëèâàåòñÿ ÷èñëî óçëîâ, ê êîòîðûì íàéäåíû ïóòè
îò óçëîâ i, i n�1, , à òàêæå âåêòîð SP spi n� || || , ñîäåðæàùèé óêàçàòåëè spi îò
óçëîâ i , i n�1, , íà ëèíåéíûå îäíîñòîðîííèå ñïèñêè, ñîñòîÿùèå èç ýëåìåíòîâ E.
Êàæäûé ýëåìåíò E ñîñòîèò èç äâóõ ïîëåé: F è AJ. Ïîëå AJ ñîäåðæèò íîìåð
óçëà, ê êîòîðîìó ïóòü íå íàéäåí, à ïîëå F ñîäåðæèò ññûëêó íà ñëåäóþùèé ýëå-
ìåíò. Ïîñëåäíèé ýëåìåíò â ñïèñêå, êàê è ïóñòîé ñïèñîê, èìååò íóëåâûå ññûëêè
(null-ññûëêè).
Ïðèâåäåì óëó÷øåííóþ âåðñèþ àëãîðèòìà SP1 ïîñòðîåíèÿ ÊÏ ïî ñòóïåí÷à-
òîìó êðèòåðèþ.
Àëãîðèòì SP2
1. T 0.
2. Äëÿ {i i n| , }�1 âûïîëíèòü ïï. 3–12.
3. Äëÿ { j j n| , }�1 , åñëè j i� , âûïîëíèòü ïï. 4–11.
4. Åñëè D i j( , )� � , òî ïåðåéòè ê ï. 5, èíà÷å ïåðåéòè ê ï. 6.
5. T i T i( ) ( ) �1; A i T i j( , ( )) ; ïåðåéòè ê ï. 11.
6. Îáðàçîâàòü íîâûé ýëåìåíò E P( ) .
7. Åñëè SP i F null( ). � , òî âûïîëíèòü ï. 8, èíà÷å âûïîëíèòü ï. 9.
8. P P2 1� ; P P1� ; P F P2. � ; ïåðåéòè ê ï. 10.
9. SP i F P( ). � ; P P1� ; ïåðåéòè ê ï. 10.
10. P AJ j. .
11. Ïåðåéòè ê ï. 3. *** Êîíåö öèêëà ïî j
12. Ïåðåéòè ê ï. 2. *** Êîíåö öèêëà ïî i
13. RMAX 1; l 0 .
14. KU 0; l l �1.
15. Äëÿ { i i n| , }�1 âûïîëíèòü ïï. 16–31.
16. Åñëè SP i F null( ). � , òî ïåðåéòè ï. 17, èíà÷å KU KU �1 ; ïåðåéòè ê ï. 31.
17. P SP i F� ( ). ; P SP i1� ( ).
18. Ïîêà P F null. � , âûïîëíèòü ïï. 19–30.
19. j P AJ . .
20. Äëÿ {m m T i| , ( )}�1 âûïîëíèòü ïï. 21–26.
21. k A i m ( , ).
22. Åñëè Q i k RMAX Q k j RMAX( , ) ( , )
, òî ïåðåéòè ê ï. 23; èíà÷å ïåðåé-
òè ê ï. 26.
23. RT Q i k Q k j �( , ) ( , ).
24. Åñëè RT Q i j RT Q i j D i j D i k D k j� � �
� �( , ) ( ( , ) ( , ) ( , ) ( , )), òî ïåðåéòè
ê ï. 25; èíà÷å ïåðåéòè ê ï. 26.
25. D i j D i k D k j( , ) ( , ) ( , ) � ; Q i j RT( , ) ; C i j C k j( , ) ( , ) .
26. Ïåðåéòè ê ï. 20. *** Êîíåö öèêëà ïî m
27. Åñëè C i j( , ) � 0, òî ïåðåéòè ê ï. 28, èíà÷å ïåðåéòè ê ï. 29.
28. T i T i( ) ( ) �1; A i T i j( , ( )) ; P F P F1. .� ; P P3 � ; P P F� . ; Îñâîáî-
äèòü ýëåìåíò E P( )3 . Ïåðåéòè ê ï. 30.
29. P P1� ; P P F� . . Ïåðåéòè ê ï. 30.
30. Ïåðåéòè ê ï. 18. *** Êîíåö öèêëà ïî j
31. Ïåðåéòè ê ï. 15. *** Êîíåö öèêëà ïî i
32. RMAX RMAX 2 .
33. Åñëè RMAX n KU n
�
�( )1 , òî ïåðåéòè ê ï. 14, èíà÷å ê ï. 34.
34. Åñëè RMAX n KU n� �
�( )1 , òî âûâåñòè ñîîáùåíèå î íåñâÿçíîñòè ñåòè.
35. Êîíåö.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5 127
 ñòðîêàõ 1–12 âûïîëíÿåòñÿ ôîðìèðîâàíèå íà÷àëüíûõ çíà÷åíèé äëÿ T , A,
SP, à â ñòðîêàõ 13–35 ñîäåðæèòñÿ îñíîâíîå òåëî àëãîðèòìà. Âåêòîð SP èñïîëüçó-
åòñÿ âî âíåøíèõ öèêëàõ ïî i è j äëÿ âûáîðà óçëîâ j , ê êîòîðûì ïóòè åùå íå íàé-
äåíû (ñòðîêè 15–31 è 18–30). Ìàòðèöà A è âåêòîð T èñïîëüçóþòñÿ âî âíóòðåííåì
öèêëå ïî m äëÿ âûáîðà íîìåðîâ óçëîâ k, ê êîòîðûì ïóòè îò i äî k óæå íàéäåíû
(ñòðîêè 20–26). Åñëè íà äàííîé èòåðàöèè íàéäåí ÊÏ îò i äî j ÷åðåç êàêîé-ëèáî
óçåë k, òî j ââîäèòñÿ â ñîîòâåòñòâóþùóþ i-þ ñòðîêó A, à èç ñïèñêà spi j-é óçåë
âûâîäèòñÿ. Ïî îêîí÷àíèè ðàáîòû àëãîðèòìà ñïèñêè spi ñòàíîâÿòñÿ ïóñòûìè,
à ñòðîêè ìàòðèöû A áóäóò ïîëíîñòüþ çàïîëíåíû (â ñëó÷àå, åñëè ñåòü ñâÿçíà).
Îïåðàöèÿ «Îáðàçîâàòü íîâûé ýëåìåíò E P( ) » â ï. 6 îçíà÷àåò îáðàçîâàíèå
ýëåìåíòà E è óñòàíîâêó íà íåãî óêàçàòåëÿ P, à îïåðàöèÿ «Îñâîáîäèòü ýëåìåíò
E P( )3 » â ï. 28 îçíà÷àåò óäàëåíèå ýëåìåíòà E, íà êîòîðûé ññûëàåòñÿ óêàçàòåëü
P3. Îïåðàöèè ñî çíàêîì � óñòàíàâëèâàþò óêàçàòåëü â ëåâîé ÷àñòè âûðàæåíèÿ íà
ýëåìåíò â ïðàâîé ÷àñòè âûðàæåíèÿ. Âûðàæåíèÿ ñ òî÷êàìè òèïà SP i F( ). , P F. ,
P AJ. îçíà÷àþò ñîîòâåòñòâóþùèå ïîëÿ ýëåìåíòîâ, íà êîòîðûå ññûëàþòñÿ óêàçà-
òåëè SP i( ) è P. Åñëè â ñòðîêå 33 îêàæåòñÿ, ÷òî RMAX n� �( )1 , òî ïðè KU n� èñ-
õîäíàÿ ñåòü íåñâÿçíà.
Äëÿ àëãîðèòìîâ SP1, Floyd è SP2 áûëè ðàçðàáîòàíû ìîäèôèöèðîâàííûå àë-
ãîðèòìû SP1S, FloydS è SP2S äëÿ ñëó÷àÿ, êîãäà ìàòðèöà R ÿâëÿåòñÿ ñèììåòðè÷-
íîé, òàê êàê ñâîéñòâî ñèììåòðè÷íîñòè ïîçâîëÿåò ñóùåñòâåííî ñîêðàòèòü âðåìÿ
íàõîæäåíèÿ ÊÏ.
Èçìåíåííûå ñòðîêè äëÿ àëãîðèòìà SP1S:
3. Äëÿ {i i n| , }� �1 1 âûïîëíèòü ïï. 4–16.
5. Äëÿ { j j i n| , }� �1 âûïîëíèòü ïï. 6–14.
6. Åñëè cij � 0 , òî ïåðåéòè ê ï. 7; èíà÷å âûïîëíèòü KS KS �1 è ïåðåé-
òè ê ï. 14.
11. D i j D i k D k j( , ) ( , ) ( , ) � ; D j i D i j( , ) ( , ) ; Q i j RT( , ) ; Q j i RT( , ) ;
C i j C k j( , ) ( , ) ; C j i C k i( , ) ( , ) .
15. Åñëè KS n i� � , òî KU KU �1.
18. Åñëè RMAX n KU n
�
� �( ) ( )1 1 , òî ïåðåéòè ê ï. 2, èíà÷å ê ï. 19.
19. Åñëè RMAX n KU n� �
� �( ) ( )1 1 , òî âûâåñòè ñîîáùåíèå î íåñâÿçíî-
ñòè ñåòè.
Èçìåíåííûå ñòðîêè äëÿ àëãîðèòìà FloydS:
2. Äëÿ { j j n| , }� �1 1 , åñëè i j� , âûïîëíèòü ïï. 3–8.
3. Äëÿ { k k j n| , }� �1 , åñëè k j i� � , âûïîëíèòü ïï. 4–7.
6. Q j k Q j i Q i k( , ) ( , ) ( , ) � ; Q k j Q j k( , ) ( , ) ; D j k D j i D i k( , ) ( , ) ( , ) � ;
D k j D j k( , ) ( , ) ; C j k C i k( , ) ( , ) ; C k j C i j( , ) ( , ) .
Èçìåíåííûå ñòðîêè äëÿ àëãîðèòìà SP2S:
4. Åñëè D i j( , )� �, òî ïåðåéòè ê ï. 5, èíà÷å ïåðåéòè ê ï. 5a.
5a. Åñëè i j� , òî ïåðåéòè ê ï. 6, èíà÷å ê ï. 11.
15. Äëÿ {i i n| , }� �1 1 âûïîëíèòü ïï. 16–31.
25. D i j D i k D k j( , ) ( , ) ( , ) � ; D j i D i j( , ) ( , ) ; Q i j RT( , ) ; Q j i RT( , ) ;
C i j C k j( , ) ( , ) ; C j i C k i( , ) ( , ) .
28. T i T i( ) ( ) � 1; T j T j( ) ( ) � 1; A i T i j( , ( )) ; A j T j i( , ( )) ; P F P F1. .� ;
P P3 � ; P P F� . ; Îñâîáîäèòü ýëåìåíò E P( )3 . Ïåðåéòè ê ï. 30.
33. Åñëè RMAX n KU n
�
� �( ) ( )1 1 , òî ïåðåéòè ê ï. 14, èíà÷å ê ï. 34.
34. Åñëè RMAX n KU n� �
� �( ) ( )1 1 , òî âûâåñòè ñîîáùåíèå î íåñâÿçíî-
ñòè ñåòè.
128 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5
ÝÊÑÏÅÐÈÌÅÍÒÀËÜÍÎÅ ÈÑÑËÅÄÎÂÀÍÈÅ ÀËÃÎÐÈÒÌÎÂ
Äëÿ ïðîâåäåíèÿ ýêñïåðèìåíòà áûëà ñîñòàâëåíà òåñòîâàÿ ïðîãðàììà íà ÿçûêå
Digital Visual Fortran (DVF) êîìïàíèè Digital Equipment Corporation â ñðåäå
Microsoft (MS) Developer Visual Studio (VS) DVF 6.1. Âî âíåøíåé ïðîãðàììå
â ðåæèìå äèàëîãà ââîäèëèñü: n — ÷èñëî óçëîâ ñåòè; �al — ÷èñëî èñõîäÿùèõ
èç êàæäîãî óçëà äóã (ñòåïåíü óçëà); ãðàíèöû èçìåíåíèÿ çíà÷åíèé âåñîâ äóã îò
MINVAL äî MAXVAL; ïàðàìåòð, óïðàâëÿþùèé âûâîäîì âõîäíûõ è âûõîäíûõ
äàííûõ. Äàëåå ñ ïîìîùüþ äàò÷èêà ñëó÷àéíûõ ÷èñåë (âñòðîåííîé ôóíêöèè
ÿçûêà RAND( ) ) ãåíåðèðîâàëèñü âåñà äóã îò MINVAL äî MAXVAL, ôîðìèðîâà-
ëèñü ìàññèâû R, D, Q, C, à òàêæå ìàññèâû A, T , SP (äëÿ àëãîðèòìîâ SP2,
SP2S). Âñÿ îïåðàòèâíàÿ ïàìÿòü, íåîáõîäèìàÿ äëÿ ðàáîòû àëãîðèòìîâ, âûäåëÿ-
ëàñü è îñâîáîæäàëàñü äèíàìè÷åñêè âî âíåøíåé ïðîãðàììå. Âðåìÿ ðàáîòû àë-
ãîðèòìîâ ôèêñèðîâàëîñü âñòðîåííîé ïîäïðîãðàììîé cputime() íåïîñðåäñòâåí-
íî äî âõîäà è ïîñëå âûõîäà èç àëãîðèòìîâ ïîñòðîåíèÿ ÊÏ. Ðàáîòà àëãîðèòìîâ
ïðîâåðÿëàñü íà ÏÝÂÌ IP-IV c òàêòîâîé ÷àñòîòîé 2,66 ÃÃö è îïåðàòèâíîé ïà-
ìÿòüþ 2 Ãá ïîä óïðàâëåíèåì îïåðàöèîííîé ñèñòåìû Windows Vista. Îòäåëüíî
ïðîâîäèëîñü ìîäåëèðîâàíèå ðåøåíèÿ çàäà÷è íà ðàçðåæåííûõ ñåòÿõ ñ ÷èñëîì
óçëîâ n �1000 ïðè èçìåíåíèè çíà÷åíèé ïàðàìåòðà �al îò 2 äî 999; ïðè èçìå-
íåíèè n îò 100 äî 1000 ïðè �al � 5 ; íà ñèëüíî ðàçðåæåííûõ ñåòÿõ ïðè �al � 2
è èçìåíåíèè n îò 500 äî 1000. Âî âñåõ ñëó÷àÿõ ïðèíèìàëîñü MINVAL � 30,
MAXVAL �120. Âñå àëãîðèòìû áûëè îôîðìëåíû â âèäå âíåøíèõ ïîäïðîãðàìì
ñ ïåðåäà÷åé ôàêòè÷åñêèõ ïàðàìåòðîâ.
Íà ðèñ. 1 ïðèâåäåíû ñîîòâåòñòâåííî ãðàôèêè èçìåíåíèÿ âðåìåíè ðàáîòû àë-
ãîðèòìîâ SP1, Floyd, SP2 è SP1S, FloydS, SP2S â çàâèñèìîñòè îò ðîñòà ñòåïåíè
óçëîâ �al îò 2 äî 999 äëÿ n �1000.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5 129
0
5
10
15
20
25
30
35
40
Â
ð
åì
ÿ
ð
àá
î
òû
,
ñ
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 200 400 600 800 999
…
…
…
1
3
2
…
�al
Ðèñ. 1. Ãðàôèê èçìåíåíèÿ âðåìåíè ðàáîòû àëãîðèòìîâ: SP1 (1), Floyd (2), SP2 (3) (à); SP1S (1),
FloydS (2), SP2S (3) (á) â çàâèñèìîñòè îò ñòåïåíè óçëîâ
0
5
10
15
20
25
30
Â
ð
åì
ÿ
ð
àá
î
òû
,
ñ
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 200 400 600 800999
…
…
…
1
3
2
… �al
à
á
130 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5
0
2
4
6
8
10
12
14
16
18
20
Â
ð
åì
ÿ
ð
àá
î
òû
,
ñ
100 200 300 400 500 600 700 800 900 1000
1
3
2
n
Ðèñ. 2. Ãðàôèê èçìåíåíèÿ âðåìåíè ðàáîòû àëãîðèòìîâ SP1 (1), Floyd (2), SP2 (3) (à) è SP1S (1),
FloydS (2), SP2S (3) (á) â çàâèñèìîñòè îò ðîñòà ÷èñëà óçëîâ ïðè �al � 5
0
1
2
3
4
5
6
7
8
9
10
Â
ð
åì
ÿ
ð
àá
î
òû
,
ñ
100 200 300 400 500 600 700 800 900 1000
1
3
2
n
à
á
0
5
10
15
20
25
30
35
40
45
Â
ð
åì
ÿ
ð
àá
î
òû
,
ñ
500 600 700 800 900 1000
1
3
2
n
Ðèñ. 3. Ãðàôèê èçìåíåíèÿ âðåìåíè ðàáîòû àëãîðèòìîâ SP1 (1), Floyd (2), SP2 (3) (à) è SP1S (1),
FloydS (2) , SP2S (3) (á) â çàâèñèìîñòè îò ðîñòà ÷èñëà óçëîâ ïðè �al � 2
0
5
10
15
20
25
30
500 600 700 800 900 1000
Â
ð
åì
ÿ
ð
àá
î
òû
,
ñ
1
3
2
n
à
á
Èç ãðàôèêîâ íà ðèñ. 1 âèäíî, ÷òî ó àëãîðèòìîâ SP1 è SP1S âû÷èñëèòåëüíàÿ ýô-
ôåêòèâíîñòü ëó÷øå, ÷åì ó àëãîðèòìîâ Floyd è FloydS óæå ïðè ñòåïåíè óçëîâ �al � 5 ,
à àëãîðèòìû SP2 è SP2S ñ ðîñòîì ñòåïåíè óçëîâ çíà÷èòåëüíî îïåðåæàþò àëãîðèòìû
Floyd è FloydS. Äëÿ áîëüøèõ çíà÷åíèé ïàðàìåòðà �al (îò 200 äî 999) àëãîðèòìû SP1,
SP1S îêàçûâàþòñÿ ëó÷øå, ÷åì SP2, SP2S. Àëãîðèòìû SP2, SP2S âñåãäà ëó÷øå àëãî-
ðèòìîâ Ôëîéäà è ñ ðîñòîì ñòåïåíè óçëîâ áûñòðåå ïîñëåäíèõ â íåñêîëüêî ðàç.
Ãðàôèêè èçìåíåíèÿ âðåìåíè ðàáîòû àëãîðèòìîâ SP1, Floyd, SP2 è SP1S,
FloydS, SP2S â çàâèñèìîñòè îò ðîñòà ÷èñëà óçëîâ îò 100 äî 1000 ïðè �al � 5 ïðè-
âåäåíû íà ðèñ. 2, à ïðè ðîñòå ÷èñëà óçëîâ îò 500 äî 1000 ïðè �al � 2 ïðåäñòàâëå-
íû íà ðèñ. 3. Äëÿ ñåòåé ñ óìåðåííîé ðàçðåæåííîñòüþ ïðè ðîñòå ÷èñëà óçëîâ â
ñåòè àëãîðèòìû SP1, SP2 è SP1S, SP2S ëó÷øå, ÷åì Floyd è FloydS. Äëÿ ñèëüíî
ðàçðåæåííûõ ñåòåé àëãîðèòìû Floyd è FloydS ñ ðîñòîì ÷èñëà óçëîâ áûñòðåå àë-
ãîðèòìîâ SP1 è SP1S, îäíàêî õóæå, ÷åì àëãîðèòìû SP2 è SP2S.
ÇÀÊËÞ×ÅÍÈÅ
Ðàññìîòðåíà óëó÷øåííàÿ âåðñèÿ àëãîðèòìà [10] ïîñòðîåíèÿ âñåõ ÊÏ â ñåòè ïî
êðèòåðèÿì: ìèíèìóì äóã â ïóòè; ìèíèìóì äëèíû ïóòè. Äîêàçàíî, ÷òî âðåìÿ
ðàáîòû àëãîðèòìà [10] ìîæåò áûòü ñîêðàùåíî çà ñ÷åò ïðèìåíåíèÿ ÀÒÄ
è óìåíüøåíèÿ ïðîñìîòðà óçëîâ âî âíóòðåííèõ öèêëàõ.
Ýìïèðè÷åñêè ïîêàçàíî, ÷òî óëó÷øåííûé àëãîðèòì íà ðàçðåæåííûõ ñåòÿõ ðàáî-
òàåò áûñòðåå, ÷åì àëãîðèòì â [10], è ïðè óâåëè÷åíèè ïëîòíîñòè ñåòè íà íåñêîëüêî
ïîðÿäêîâ ïðåâûøàåò ïî ñêîðîñòè ðàáîòû ìîäèôèöèðîâàííûé àëãîðèòì Ôëîéäà.
 öåëîì ýêñïåðèìåíò ïîêàçàë âûñîêóþ âû÷èñëèòåëüíóþ ýôôåêòèâíîñòü ïðåä-
ëîæåííîãî àëãîðèòìà, êîòîðûé ìîæåò áûòü âêëþ÷åí â ñîñòàâ òèïîâîãî èíñòðóìåí-
òàðèÿ ðàçðàáîò÷èêà è ñ óñïåõîì ïðèìåíÿòüñÿ ïðè ðåøåíèè ïðàêòè÷åñêèõ çàäà÷ íà-
õîæäåíèÿ äâóõêðèòåðèàëüíûõ ÊÏ íà ãðàôàõ è ñåòÿõ áîëüøîé ðàçìåðíîñòè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. H a n s e n P . Bicriterion path problems // Multiple Criteria Decision Making Theory and
Application (Ed. G. Fandel and T. Gal). — Berlin: Springer, 1979. — P. 109–127.
2. W a r b u r t o n A . Approximation of Pareto optima in multiple-objective, shortest-path problems //
Oper. Res. — 1987. — 35, N 1. — P. 70–79.
3. E h r g o t t M . , G a n d i b l e u x X . Multiple criteria optimization — state of the art annotated
bibliographic surveys. — Boston, MA: Kluwer, 2002. — 496 ð.
4. Ê í ÿ ç å â à Í . À . Èñïîëüçîâàíèå ëîãè÷åñêèõ îïåðàöèé äëÿ ïîèñêà îïòèìàëüíûõ ïóòåé â ñåòè
// II Âñåñîþç. ñîâåùàíèå «Ìåòîäû è ïðîãðàììû ðåøåíèÿ îïòèìèçàöèîííûõ çàäà÷ íà ãðàôàõ
è ñåòÿõ», 24–26 àâãóñò 1982 ã., Óëàí-Óäý: Òåç. äîêë. — Íîâîñèáèðñê, 1982. – ×. 1: Òåîðèÿ, àë-
ãîðèòìû. — Ñ. 85–86.
5. Ä î á ð î ë þ á î â B . B . , Ï å ä ÿ ø Â . À . Ñåòåâîé àëãîðèòì ïîñòðîåíèÿ ïóòåé ñ ìèíèìàëüíûì
÷èñëîì òðàíçèòíûõ óçëîâ è ñ ìàêñèìàëüíîé ïðîïóñêíîé ñïîñîáíîñòüþ // Âû÷èñë. ñðåäñòâà
â òåõíèêå è ñèñòåìàõ ñâÿçè. — 1979. — ¹ 4. — C. 129–132.
6. M o o r e E . F . The shortest path through a mace // Proceed. of the Intern. Symp. on the Theory of
Switching. — Cambridge Harvard University Press, 1959. — Part II. — P. 285–292.
7. À õ î À . , Õ î ï ê ð î ô ò Ä æ . , Ó ë ü ì à í Ä æ . Ïîñòðîåíèå è àíàëèç âû÷èñëèòåëüíûõ àëãî-
ðèòìîâ. — Ì.: Ìèð, 1979. — 586 ñ.
8. F l o y d R . W . Algorithm 97: shortest path // Comm. ACM. — 1962. — 5. — P. 345.
9. D i j k s t r a F . W . A note on two problems in connection with graphs // Numerical mathematic. —
1959. — N 1. — P. 269–271.
10.  à ñ ÿ í è í B . A . , Ñ à â å í ê î â À . È . Àëãîðèòì ïîñòðîåíèÿ êðàò÷àéøèõ ïóòåé íà ñåòè ïî
ñòóïåí÷àòîìó êðèòåðèþ // Äèñêðåò. è ýðãàòè÷. ñèñòåìû óïðàâëåíèÿ: Ñá. íàó÷. òð. — Êèåâ,
1983. — C. 40–49.
11. B e l l m a n R . E . On a routing problem // Quart. Appl. Math. — 1958. — 16, N 1. — P. 87–90.
12. S h i m b e l A . Applications of matrix algebra to communication nets // Bulletin of Mathematical
Biophysics. — 1951. — 13. — P. 165–178.
Ïîñòóïèëà 30.01.2014
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5 131
|