назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [ 81 ] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


81

1 2 ... j ... п

1 2 ... j ... л

So =

Основной этап к. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения треугольного оператора ко всем элементам dtj матрицы Dk r Если выполняется неравенство

dik + dkj < d,j> (i*k,j*kni*j), то делаем следующее:

a) создаем матрицу Dk путем замены в матрице Dk 1 элемента dtj суммой dlk + dkj,

b) создаем матрицу Sk, меняя в матрице S4 j элемент s, на h. Полагаем k = k + 1 и повторяем этап ft.

Поясним действия, выполняемые на k-м этапе алгоритма, представив матрицу Dk j так, как она показана на рис. 6.20. На этом рисунке строка k и столбец k являются ведущими. Стро-ка i- любая строка с номером от 1 до А - 1, а строка р - произвольная строка с номером от k + 1 до л. Аналогично столбец / представляет любой столбец с номером от 1 до k - 1, а столбец q - произвольный столбец с номером от k + 1 до л. Треугольный оператор выполняется следующим образом. Если сумма элементов ведущих строки и столбца (показанных в квадратиках) меньше элементов, находящихся на пересечении столбца и строки (показаны в кружках), соответствующих рассматриваемым ведущим элементам, то расстояние (элемент в кружке) заменяется суммой расстояний, представленных ведущими элементами.

После реализации л этапов алгоритма определение по матрицам Dn и Sn кратчайшего пути между узлами i и j выполняется по следующим правилам.

1. Расстояние между узлами i и j равно элементу dtJ в матрице Dn.

2. Промежуточные узлы пути от узла i к узлу j определяем по матрице Sn. Пусть s0 = k, тогда имеем путь i -> k -> /. Если далее slk = k и skj = j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу



Столбец j

Строка i

Ведущая строка

Строка р

Ведущий столбец

Столбец Q

Рис. 6.20. Реализация треугольного оператора

Пример 6.3.5

Найдем для сети, показанной на рис. 6.21, кратчайшие пути между любыми двумя узлами. Расстояния между узлами этой сети проставлены на рисунке возле соответствующих ребер. Ребро (3, 5) ориентированно, поэтому не допускается движение от узла 5 к узлу 3. Все остальные ребра допускают движение в обе стороны.

Рис. 6.21. Сеть для примера 6.3.5

ЭтапО. Начальные матрицы D0 и S0 строятся непосредственно по заданной схеме сети. Матрица D0 симметрична, за исключением пары элементов и d53, где d63 = ос (поскольку невозможен переход от узла 5 к узлу 3).

Do 3

So 3

»«о

а>



Этап 1. В матрице D0 выделены ведущие строка и столбец с номером k = 1.

Затемненными представлены элементы d23 и d32, единственные среди элементов матрицы D0, значения которых можно улучшить с помощью треугольного оператора. Таким образом, чтобы на основе матриц D0 и S0 получить матрицы D, и Sv выполняем следующие действия.

1. Заменяем d23 на d2X + dl3 = 3 + 10 = 13 и устанавливаем s23 = 1.

2. Заменяем d32 на d3l + dl2 = 10 + 3 = 13 и устанавливаем s32 = 1. Матрицы D, и S, имеют следующий вид.

D, 3

Si 3

Этап 2. Полагаем k = 2; в матрице D; выделены ведущие строка и столбец. Треугольный оператор применяется к элементам матриц D, и выделенным затенением. В результате получаем матрицы D2 и S2.

D2 3

i:13v:

□0

Этап 3. Полагаем k = 3; в матрице D2 выделены ведущие строка и столбец.

Треугольный оператор применяется к затемненным элементам матриц D2 и S2. В результате получаем матрицы D3 и S3.

D3 3

S3 3

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [ 81 ] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]