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


[Старт] [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]


80

Временный статус метки [40, 3] узла 4 заменяется постоянным (ut = 40).

Этап 3. Из узла 4 можно достичь узлов 2 и 5. После вычисления меток получим следующий их список.

Узел Метка Статус метки

1 [0, -] Постоянная

2 [40 + 15, 4] = [55, 4] Временная

3 [30,1] Постоянная

4 [40,3] Постоянная

5 [90, 3] или [40 + 50, 4] = [90, 4] Временная

Временная метка [100, 1], полученная узлом 2 на втором этапе, изменена на [55, 4]. Это указывает на то, что найден более короткий путь к этому узлу (проходящий через узел 4). На третьем этапе узел 5 получает две метки с одинаковым значением расстояния иь = 90.

Этап 4. Из узла 2 можно перейти только в узел 3, но он уже имеет постоянную метку, которую нельзя изменить. Поэтому на данном этапе получаем такой же список меток, как и на предыдущем, но с единственным изменением: метка узла 2 получает статус постоянной. С временной меткой остается только узел 5, но, так как из этого узла нельзя попасть ни в какой другой, процесс вычислений заканчивается.

Алгоритм позволяет проводить вычисления непосредственно на схеме сети, как показано на рис. 6.15.

[55,4](3)

() = шаг

Рис. 6.15. Применение алгоритма Дейкстры

Кратчайший маршрут между узлом 1 и любым другим узлом определяется начиная с узла назначения путем прохождения их в обратном направлении с помощью информации, представленной в постоянных метках. Например, для определения кратчайшего маршрута между узлами 1 и 2 получаем такую обратную последовательность узлов

(2) -> [55, 4] -> (4) -> [40, 3] -> (3) -> [30, 1] -> (1). Таким образом, получаем путь 1 -> 3 -> 4 -> 2 общей длиной 55 миль.



Программа TORA также может применять алгоритм Дейкстры для решения сетевых задач. Для этого в меню SOLVE/MODIFY выберите команду Solve problem Iterations1 Dijkstras algoritm (Алгоритм Дейкстры). На рис. 6.16 показано выходное окно TORA с решением задачи из примера 6.3.4 (файл ch6ToraDijkstraEx6-3-4.txt).

• TV*« II WoifcMo ..Fdr-IMTlMOifati-.t.t. I 4 I.I

NETWOHK MCIDEIS

Рис. 6.16. Решение задачи из примера 6.3.4

УПРАЖНЕНИЯ 6.3.2

1. На рис. 6.17 показана транспортная сеть, соединяющая восемь городов, и расстояния между ними. Найдите кратчайшие маршруты между следующими городами.

a) Города 1 и 8.

b) Города 1 и 6.

c) Города 4 и 8.

d) Города 2 и 6.

2. Найдите кратчайшие пути между узлом 1 и всеми остальными узлами сети, представленной на рис. 6.18.

3. Найдите оптимальное решение задачи из упражнения 6.3.1.1.

4. Найдите оптимальное решение задачи из упражнения 6.3.1.2.

5. Найдите оптимальное решение задачи из упражнения 6.3.1.4.



Рис. 6.17. Сеть для задачи из упражнения 1 6

Рис. 6.18. Сеть для задачи из упражнения 2

Алгоритм Флойда. Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя узлами сети. В этом алгоритме сеть представлена в виде квадратной матрицы с п строками и п столбцами. Элемент (£, /) равен расстоянию dtj от узла i к узлу /, которое имеет конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае.

Покажем сначала основную идею метода Флойда. Пусть есть три узла i, j и k и заданы расстояния между ними (рис. 6.19). Если выполняется неравенство dtj + djk < dllt, то целесообразно заменить путь i -> k путем i->;->ft. Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.

Рис. 6.19. Треугольный оператор Флойда Алгоритм Флойда требует выполнения следующих действий.

Этап 0. Определяем начальную матрицу расстояний D0 и матрицу последовательности узлов S0. Диагональные элементы обеих матриц помечаются знаком "-", показывающим, что эти элементы в вычислениях не участвуют. Полагаем k = 1.

[Старт] [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]