Теория графов и комбинаторика

ji.afui лао взрийнн У и W . Тре^^уотся найт); (I/"" ^)~п у т ь , iiKft'inpii; наименьшую органу. /ui'opii7t.i роийняя: 1. Иа, .нуморовпгь воршшш т'рафа 9 так, чтобы вершина У яолучмг! Помар О . Обозначить iT через 1/^, При этом вершина О- пс-"пит некоторый номер И (и''»1)'иЬ 2. Бершпнам Ус , i =<?,<,.•• приовоить метки Я^ :ак, что Лв "О ; Я:. - + СО , о о, 3. Найти дату Ti'^ ^ I дай которой , ti , 9; »w-H:n'b значекпе матки конца на новоз меньшее знйчвяие по асргд^'ла; -f icj. . Считаем, что « - = 0 . 4. Процесс изкенйпия меток вершнн продолжать до тех пор, когда V r i . j . ' S r ) . 5. Нййти поолздователъность вершин 'Из условий: ^Р( ^ ^ ~ ^ Ч I % ^ Д- ^Рг.+ 5 '^Р^ЕГ ^Р^+^Р^^Р^^^^^ЯР^^^- Пекоторая и з вершин этой послвдовательяоохн Тр оовпадет о Vo Путь <•', i7p,, а ) имеет нашеныпую длину, равную L(^0 -^ п . Замачания. Начальные значения I "' T OK воех эргаи, кроме "Do, pai'Hii со . Прн конкретных расчетах бзоконечнооть надо понимать как достаточно большое число, например, машрпшую бесконачнооть. качоотнв начальных меток i. жет быть взято чиоло L , равное оу№Д0 д и ш воех д у г графа 1? . Из п . п . З и 4 алгоритма следует, что окончаувльные значения меток варшна •довлетворяют уоловиям: Д г: VVlt-H { 2 i +^ u } { Ч Л у " ( 12Л) <1 ЧеГ'Ьг^у ^ ^ . Окончательные значения ыеток вершин равны длинам крат-j чайтих ( 1 ^ - 1 ^ )~пухвй .. Если для некотор .Д вершины метка A j (пооле выцслне!шя п . ^ , то это означает, что в графе <?, -путей не оущеотвует. Из ы.лаанного следует, что раоомат- ривавмый адаопитм, предложенный Двйкотрой [ i s j , п^звoля6т найти пут- нвшденьшал дпаны от вершины V до любой другой вершины, 0ОЛИ они оущеотвувт. Очевидно, еоли V i f ^ P = i ) ..то этот алгоритм дает путь с наименьшим числом ,дуг. , •