Пътища в контурна графика
За отворен граф с произволни тегла на дъги, проблемът с намирането на най-краткия път може да бъде решен в ОТНОСНО(м) стъпки. Помислете за модел без контурна графика (Фигура 10.5).
Фигура: 10.5. Графика на модела
Всяка отворена графика има следното свойство: нейните върхове могат да бъдат преномерирани, така че всяка дъга ще премине от върх с по-нисък номер към връх с по-голям номер.
Тази номерация ще се нарича правилна. За нашата моделна графика пример за възможно правилно номериране е показан на фиг. 10.6.
Фигура: 10.6. Правилно номериране
Доказателство за това свойство ще бъде правилният алгоритъм за номериране.
Алгоритъмът се основава на следния прост факт: има поне един връх в неконтролирана графика, в която не влиза нито една дъга (в противен случай в графиката ще има контур).
Поставяме всички такива върхове в стека. Тогава
1) извадете произволен връх от стека;
2) задайте му номер 1;
3) премахнете го от графиката заедно с всички дъги, които го напускат.
След операцията по премахване на дъги могат да се появят нови върхове, в които не влиза нито една дъга. Тези върхове се изтласкват върху стека, след което от стека се изскача произволен връх, на него се присвоява следващият номер и т.н.
Ясно е, че резултатът ще бъде правилната номерация, тъй като всеки връх u получава число в момента, когато останалите неномерирани върхове v (по-късно ще получат по-големи номера) или не са свързани чрез дъги с u, или дъгата върви в посока (u→v).
Не е толкова очевидно защо всички върхове ще получат числа:
ако последният връх е премахнат от стека и в графиката, получена след премахването на този връх и дъгите, които го напускат, всички върхове имат дъги, които ги въвеждат, тогава те никога няма да отидат в стека и никога няма да получат числа.
Факт е, че когато премахвате върхове и дъги от неконтролирана графика, винаги получавате неконтролирана графика и в нея има поне един връх, без да влизат дъги в нея. Следователно всеки връх определено ще влезе в стека и ще получи съответното число.
Тъй като произволен връх се изскача от стека, принципът на стека не е задължителен и е избран само за удобство.
Данни: Безконтурен диграф G= дадено от списъци с честота SLED[v], v Î V.
Резултати: За всеки връх v нов номер [v] такива, че числата [v] са правилното номериране на графиката G.
2 за vÎV направете INP [v]: = 0;
4 за vÎSLED [u] do
8 ако INP [v] = 0, тогава STACK Ü v;
10 докато STACK <> 0 направи
15 за vÎSLED [u] do
18 ако INP [v] = 0, тогава STACK Ü v;
Всички дъги на графиката се анализират два пъти: в цикъл 3-5, за да се преброи броят на входящите дъги INP[v], в цикъл 10–20, където премахването на дъги от графиката се заменя с намаляване на числата INP[v].
По този начин изчислителната сложност на алгоритъма е пропорционална на броя на дъгите, т.е. се равнява ОТНОСНО(м) стъпки.