Вступление
Как мы видели в предыдущем посте, алгоритм Дейкстры очень полезен, когда речь идет о поиске всех кратчайших путей во взвешенном графе. Однако у него есть одна серьезная проблема! Очевидно, что это не работает правильно при работе с отрицательными длинами ребер.
Мы знаем, что алгоритм отлично работает, когда дело доходит до положительных ребер, и это абсолютно нормально, потому что мы пытаемся оптимизировать неравенство треугольника.
Поскольку все ребра положительны, мы получаем ближайший!
Поскольку алгоритм Дейкстры обычно использует приоритетную очередь, мы сначала получаем самое короткое смежное ребро с начальной точкой. В нашем очень простом примере мы сначала получим ребро длиной 3 -> (S, A).
Однако, когда дело доходит до отрицательных граней, мы не можем использовать более приоритетные очереди, поэтому нам нужно другое, но работающее решение.
обзор
Решение было опубликовано Ричардом Э. Беллманом и Лестером Фордом-младшим в 1958 году в их публикации «О проблеме маршрутизации», и его довольно просто объяснить и понять. Поскольку мы можем расставить приоритеты ребер по их длине, единственное, что нам нужно сделать, — это рассчитать все пути. И чтобы быть уверенным, что наш алгоритм найдет все пути правильно, мы повторим это N-1 раз, где N — число вершин (| V | = N)!
Алгоритм Беллмана-Форда не использует приоритетные очереди! Действительно, они бесполезны, так как ближайший узел в очереди может иметь более короткий путь, проходящий через другой узел!
На этом очень простом изображении мы видим, как Беллман-Форд решает проблему. Сначала мы получаем расстояния от S до A и B, которые соответственно равны 3 и 4, но есть более короткий путь к A, который проходит через B, и он (S, B) + (B, A) = 4 — 2 = 2
Код
Вот код на PHP . Обратите внимание, что на этот раз мы используем матрицу смежности и дополнительный массив расстояний. Важно (для ориентированных графов, и наш граф на этот раз направлен) поставить положительное значение A [j] [i], если A [i] [j] отрицательно. Обратите внимание на случай для A [1] [2]!
define('INFINITY', 10000000);
$matrix = array(
0 => array( 0, 3, 4),
1 => array( 0, 0, 2),
2 => array( 0, -2, 0),
);
$len = count($matrix);
$dist = array();
function BellmanFord(&$matrix, &$dist, $start)
{
global $len;
foreach (array_keys($matrix) as $vertex) {
$dist[$vertex] = INFINITY;
if ($vertex == $start) {
$dist[$vertex] = 0;
}
}
for ($k = 0; $k < $len - 1; $k++) {
for ($i = 0; $i < $len; $i++) {
for ($j = 0; $j < $len; $j++) {
if ($dist[$i] > $dist[$j] + $matrix[$j][$i]) {
$dist[$i] = $dist[$j] + $matrix[$j][$i];
}
}
}
}
}
BellmanFord($matrix, $dist, 0);
// [0, 2, 4]
print_r($dist);
сложность
Сложность явно O (n 3 ), что следует непосредственно из кода выше.
заявка
На самом деле этот алгоритм очень полезен, и он не только работает с отрицательными весами, но также может помочь нам найти отрицательные циклы на графике.
Отрицательный цикл можно найти с помощью алгоритма Беллмана-Форда!
Это делается с помощью простой проверки после основного цикла.
for ($i = 0; $i < $len; $i++) {
for ($j = 0; $j < $len; $j++) {
if ($dist[$i] > $dist[$j] + $matrix[$j][$i]) {
echo 'The graph contains a negative cycle!';
}
}
}
И вот полный код.
$matrix = array(
0 => array( 0, 3, 4),
1 => array( 0, 0, 2),
2 => array( 0, -2, 0),
);
$len = count($matrix);
$dist = array();
function BellmanFord(&$matrix, &$dist, $start)
{
global $len;
foreach (array_keys($matrix) as $vertex) {
$dist[$vertex] = INFINITY;
if ($vertex == $start) {
$dist[$vertex] = 0;
}
}
for ($k = 0; $k < $len - 1; $k++) {
for ($i = 0; $i < $len; $i++) {
for ($j = 0; $j < $len; $j++) {
if ($dist[$i] > $dist[$j] + $matrix[$j][$i]) {
$dist[$i] = $dist[$j] + $matrix[$j][$i];
}
}
}
}
for ($i = 0; $i < $len; $i++) {
for ($j = 0; $j < $len; $j++) {
if ($dist[$i] > $dist[$j] + $matrix[$j][$i]) {
echo 'The graph contains a negative cycle!';
}
}
}
}
BellmanFord($matrix, $dist, 0);
// [0, 2, 4]
print_r($dist);
Похожие сообщения:
- Компьютерные алгоритмы: кратчайший путь Дейкстры в графе
- Компьютерные алгоритмы: кратчайший путь в графе
- Компьютерные алгоритмы: поиск по ширине графика
- Компьютерные алгоритмы: поиск по глубине графика
- Компьютерные алгоритмы: Graph Best-First Search