Cтраница 4
Флойда нахождения кратчайших путей между всеми парами вершин может быть использован и для обнаружения в графе циклов отрицательного веса. Кроме того, в тех случаях, когда в графе имеется вершина яг из которой достижимы все остальные вершины этого графа, для нахождения циклов отрицательного веса можно также использовать алгоритм из разд. Если не все вершины графа С достижимы из я ( например, когда б является неориентированным графом, составленным не менее чем из двух связных компонент), то алгоритм разд. В этом случае циклы отрицательного веса, лежащие в других компонентах, не будут обнаружены. [46]
Флойда нахождения кратчайших путей между всеми парами вершин может быть использован и для обнаружения в графе циклов отрицательного веса. Кроме того, в тех случаях, когда в графе имеется вершина sr из которой достижимы все остальные вершины этого графа, для нахождения циклов отрицательного веса можно также использовать алгоритм из разд. Если не все вершины графа G достижимы из s ( например, когда G является неориентированным графом, составленным не менее чем из двух связных компонент), то алгоритм разд. В этом случае циклы отрицательного веса, лежащие в других компонентах, не будут обнаружены. [47]
Используя алгоритм кратчайшего пути, найти кратчайшие пути 5J1 от х - 1 к t, исключая из рассмотрения вершины sr я. Если существует несколько кратчайших путей, взять в качестве 8г один из них. [48]
Алгоритм нахождения кратчайшего пути, Вычислительные системы, Новосибирск, 1963, вып. [49]
Предшественник алгоритма кратчайшего пути из разд. [50]
Для отыскания кратчайшего пути построим точку А ( см. рис. 53), расположенную симметрично точке А относительно плоскости MN. [51]
Длины uiN кратчайших путей методом нумерации ( маркировки) узлов определяются следующим образом. Вес узла N принимается тождественно равным нулю. [52]
Алгоритм определения кратчайших путей по этому методу состоит в следующем. [53]
Алгоритм нахождения кратчайшего пути, приведенный в разд. [54]
Алгоритм нахождения кратчайшего пути, который применим к графу с ребрами произвольной длины, а также алгоритм построения стягивающего дерева с минимальной стоимостью ( который является усовершенствованием второго алгоритма из разд. [55]
Найти длину кратчайшего пути, ведущего по поверхности куба с ребром 1 из одной его вершины в противоположную. [56]
Результат вычисления кратчайшего пути даст табл. 19.3. Решением задачи целочисленного программирования является ( хв, xv) с хв B b - B Nxjyr. Мы показали, что решение состоит из двух частей и что вторая часть является периодической поправкой. [57]
Модель выбора кратчайшего пути ( разд. Рассмотрим пример, представленный на рис. 6.8. Предположим, что стоимости переезда от одного узла к другому являются случайными величинами, а переезд вдоль каждой дуги занимает один период. Пусть в течение каждого из трех первых периодов стоимость переезда из узла i в узел / равняется либо С; - с вероятностью ptj, либо dtj с вероятностью 1 - Pij. После третьего периода стоимость переезда из узла z в узел / равняется либо etj с вероятностью д - 7 -, либо / j с вероятностью 1 - qtj. Допустим, что стоимость переезда вдоль той или иной дуги в каждый из периодов не зависит от стоимости переезда вдоль этой дуги в другие периоды. [58]
Модель выбора кратчайшего пути ( разд. Допустим, что при любом значении t величины CD являются полностью не зависимыми от всех прочих случайных элементов. Предположим, что информацию относительно фактических значений сц можно получить только по прибытии в узел г. Задача заключается в выборе маршрута из узла 8 ( источник) в узел 1 ( сток), минимизирующего математическое ожидание суммарных затрат. Примечание: не пытайтесь выбирать весь маршрут целиком в начале планового периода; на каждом отрезке планового периода дуга выбирается в зависимости от того, какого узла мы достигли и каковыми являются соответствующие стоимостные характеристики. [59]