Подготовка к алгоритмическим задачам

Алгоритм Беллмана-Форда: подробный разбор решения

14 мин чтения

алгоритмы

графы

поиск кратчайших путей

динамическое программирование

отрицательные циклы

Почему этот алгоритм важен?

Алгоритм Беллмана-Форда — это фундаментальный алгоритм для поиска кратчайших путей, который позволяет оценить:

🗺️ Способность работать с графами, содержащими рёбра с отрицательным весом
🔄 Умение обнаруживать отрицательные циклы в графе
⚡ Навыки оптимизации алгоритмов поиска кратчайших путей
🧠 Понимание принципов динамического программирования
💼 Практические навыки решения сетевых задач и задач маршрутизации

Постановка задачи

Классическая формулировка:

Дан взвешенный ориентированный граф G = (V, E), где V — множество вершин, а E — множество рёбер. Каждое ребро (u, v) имеет вес w(u, v), который может быть отрицательным. Требуется найти кратчайшие пути от заданной исходной вершины s до всех остальных вершин графа. В случае обнаружения отрицательного цикла, достижимого из s, алгоритм должен сообщить о его наличии.

Математическая формулировка:

Для каждой вершины v ∈ V найти путь от s до v такой, что сумма весов рёбер на этом пути минимальна.

Где:

s — исходная вершина
V — множество вершин графа
E — множество рёбер графа
w(u, v) — вес ребра (u, v)

Примеры:

// Первый пример ✅
Input: 
edges = [[0, 1, 5], [0, 2, 2], [1, 3, 3], [2, 1, -2], [2, 3, 6]]
vertices = 4
source = 0

Output: [0, 0, 2, 3]
Distances: [0, 0, 2, 3]
Объяснение: Кратчайшие расстояния от вершины 0: до 0 - 0, до 1 - 0, до 2 - 2, до 3 - 3

// Второй пример с отрицательным циклом ⚠️
Input:
edges = [[0, 1, 3], [1, 2, -4], [2, 0, 1]]
vertices = 3
source = 0

Output: "Negative cycle detected"
Объяснение: Граф содержит отрицательный цикл (0 -> 1 -> 2 -> 0), суммарный вес которого равен 0

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Подходы к решению

Решение 1: Базовая реализация алгоритма Беллмана-Форда 🔍

function bellmanFord(edges, vertices, source) {
  // Инициализация расстояний
  const distance = Array(vertices).fill(Infinity);
  const predecessor = Array(vertices).fill(null);
  distance[source] = 0;
  
  // Релаксация рёбер |V| - 1 раз
  for (let i = 0; i < vertices - 1; i++) {
    for (const [from, to, weight] of edges) {
      if (distance[from] !== Infinity && distance[from] + weight < distance[to]) {
        distance[to] = distance[from] + weight;
        predecessor[to] = from;
      }
    }
  }
  
  // Проверка на наличие отрицательных циклов
  for (const [from, to, weight] of edges) {
    if (distance[from] !== Infinity && distance[from] + weight < distance[to]) {
      return { hasNegativeCycle: true, message: "Negative cycle detected" };
    }
  }
  
  return {
    hasNegativeCycle: false,
    distances: distance,
    predecessors: predecessor
  };
}

// Вызов функции
function findShortestPaths(edges, vertices, source) {
  const result = bellmanFord(edges, vertices, source);
  
  if (result.hasNegativeCycle) {
    return result.message;
  }
  
  // Восстановление путей
  const paths = Array(vertices).fill().map(() => []);
  
  for (let v = 0; v < vertices; v++) {
    let current = v;
    while (current !== null && current !== source) {
      paths[v].unshift(current);
      current = result.predecessors[current];
    }
    
    if (current === source) {
      paths[v].unshift(source);
    } else {
      paths[v] = []; // Вершина недостижима
    }
  }
  
  return {
    distances: result.distances,
    paths: paths
  };
}

Анализ решения:

✅ Корректно находит кратчайшие пути для всех вершин графа

✅ Обнаруживает отрицательные циклы

✅ Простой для понимания алгоритм с чёткими шагами

❌ Временная сложность O(|V| × |E|) может быть неэффективна для больших графов

❌ Избыточные проверки для рёбер, которые не влияют на результат

Решение 2: Оптимизированная реализация с ранней остановкой 🚀

function bellmanFordOptimized(edges, vertices, source) {
  // Инициализация расстояний
  const distance = Array(vertices).fill(Infinity);
  const predecessor = Array(vertices).fill(null);
  distance[source] = 0;
  
  let updated = true;
  let iteration = 0;
  
  // Релаксация рёбер с ранней остановкой
  while (updated && iteration < vertices - 1) {
    updated = false;
    
    for (const [from, to, weight] of edges) {
      if (distance[from] !== Infinity && distance[from] + weight < distance[to]) {
        distance[to] = distance[from] + weight;
        predecessor[to] = from;
        updated = true;
      }
    }
    
    iteration++;
    
    // Если на текущей итерации не было обновлений, можно остановиться
    if (!updated) {
      break;
    }
  }
  
  // Проверка на наличие отрицательных циклов
  for (const [from, to, weight] of edges) {
    if (distance[from] !== Infinity && distance[from] + weight < distance[to]) {
      // Находим вершины, входящие в отрицательный цикл
      const cycle = detectNegativeCycle(edges, vertices, distance);
      return { 
        hasNegativeCycle: true, 
        message: "Negative cycle detected",
        cycle: cycle
      };
    }
  }
  
  return {
    hasNegativeCycle: false,
    distances: distance,
    predecessors: predecessor,
    iterations: iteration
  };
}

// Функция для определения вершин, входящих в отрицательный цикл
function detectNegativeCycle(edges, vertices, distance) {
  // Создаём копию расстояний для дополнительной релаксации
  const tempDist = [...distance];
  const affected = new Set();
  
  // Релаксируем рёбра ещё раз для выявления затронутых вершин
  for (const [from, to, weight] of edges) {
    if (tempDist[from] !== Infinity && tempDist[from] + weight < tempDist[to]) {
      tempDist[to] = tempDist[from] + weight;
      affected.add(to);
    }
  }
  
  // Выполняем обход в глубину для поиска вершин в цикле
  if (affected.size > 0) {
    const visited = Array(vertices).fill(false);
    const cycle = [];
    
    // Начинаем с любой затронутой вершины
    const startVertex = [...affected][0];
    
    // Детали реализации DFS для восстановления цикла...
    // (код обхода в глубину для поиска цикла)
    
    return cycle;
  }
  
  return [];
}

Характеристики:

✅ Значительное ускорение для графов, где кратчайшие пути находятся за меньшее число итераций

✅ Предоставляет информацию о конкретных вершинах в отрицательном цикле

✅ Выполняет только необходимое количество итераций

❌ Немного более сложная реализация из-за дополнительной логики

❌ Обнаружение и восстановление цикла требует дополнительных операций

Решение 3: Реализация с изоляцией источника для разреженных графов 📈

function bellmanFordSparse(edges, vertices, source) {
  // Преобразуем список рёбер в список смежности для эффективной обработки
  const adjList = Array(vertices).fill().map(() => []);
  
  for (const [from, to, weight] of edges) {
    adjList[from].push({ to, weight });
  }
  
  // Инициализация расстояний
  const distance = Array(vertices).fill(Infinity);
  const predecessor = Array(vertices).fill(null);
  distance[source] = 0;
  
  // Очередь для вершин, расстояния до которых были обновлены
  let queue = [source];
  // Счётчик посещений для обнаружения отрицательных циклов
  const visitCount = Array(vertices).fill(0);
  // Флаги для вершин в очереди
  const inQueue = Array(vertices).fill(false);
  inQueue[source] = true;
  
  while (queue.length > 0) {
    const current = queue.shift();
    inQueue[current] = false;
    visitCount[current]++;
    
    // Если вершина обрабатывается слишком много раз, вероятно есть отрицательный цикл
    if (visitCount[current] > vertices) {
      return { hasNegativeCycle: true, message: "Negative cycle detected" };
    }
    
    // Релаксация исходящих рёбер
    for (const { to, weight } of adjList[current]) {
      if (distance[current] + weight < distance[to]) {
        distance[to] = distance[current] + weight;
        predecessor[to] = current;
        
        // Добавляем вершину в очередь, если её ещё там нет
        if (!inQueue[to]) {
          queue.push(to);
          inQueue[to] = true;
        }
      }
    }
  }
  
  return {
    hasNegativeCycle: false,
    distances: distance,
    predecessors: predecessor
  };
}

Преимущества и недостатки:

✅ Более эффективен для разреженных графов (где |E| << |V|²)

✅ Обрабатывает только достижимые вершины и вершины, для которых расстояния изменились

✅ Раннее обнаружение отрицательных циклов

❌ Требует дополнительной памяти для хранения списка смежности

❌ Может быть медленнее для плотных графов из-за большего количества операций

Решение 4: Параллельная реализация для больших графов 🔧

function bellmanFordParallel(edges, vertices, source, numThreads = 4) {
  // Примечание: это псевдокод, демонстрирующий идею параллельной реализации
  // Реальная многопоточность в JavaScript ограничена архитектурой
  
  // Инициализация расстояний
  const distance = Array(vertices).fill(Infinity);
  const predecessor = Array(vertices).fill(null);
  distance[source] = 0;
  
  // Разделение рёбер на части для параллельной обработки
  const edgeChunks = divideEdgesIntoChunks(edges, numThreads);
  
  for (let i = 0; i < vertices - 1; i++) {
    // Параллельное выполнение релаксации для каждой части рёбер
    const results = edgeChunks.map(chunk => 
      relaxEdgesParallel(chunk, distance, predecessor)
    );
    
    // Объединение результатов параллельных вычислений
    const anyUpdated = mergeRelaxationResults(results, distance, predecessor);
    
    // Если не было обновлений, можно остановиться раньше
    if (!anyUpdated) {
      break;
    }
  }
  
  // Проверка на наличие отрицательных циклов
  const negCycleCheck = checkNegativeCycleParallel(edges, distance);
  
  return {
    hasNegativeCycle: negCycleCheck.hasNegativeCycle,
    distances: negCycleCheck.hasNegativeCycle ? null : distance,
    predecessors: negCycleCheck.hasNegativeCycle ? null : predecessor,
    cycle: negCycleCheck.cycle
  };
}

// Вспомогательные функции для параллельной реализации
function divideEdgesIntoChunks(edges, numChunks) {
  // Разделение рёбер на примерно равные части
  const chunkSize = Math.ceil(edges.length / numChunks);
  const chunks = [];
  
  for (let i = 0; i < edges.length; i += chunkSize) {
    chunks.push(edges.slice(i, i + chunkSize));
  }
  
  return chunks;
}

function relaxEdgesParallel(edgeChunk, distance, predecessor) {
  // Локальные копии для отслеживания изменений
  const localDistance = [...distance];
  const localPredecessor = [...predecessor];
  let updated = false;
  
  for (const [from, to, weight] of edgeChunk) {
    if (localDistance[from] !== Infinity && localDistance[from] + weight < localDistance[to]) {
      localDistance[to] = localDistance[from] + weight;
      localPredecessor[to] = from;
      updated = true;
    }
  }
  
  return {
    updated,
    distance: localDistance,
    predecessor: localPredecessor
  };
}

function mergeRelaxationResults(results, distance, predecessor) {
  let anyUpdated = false;
  
  for (const result of results) {
    if (result.updated) {
      anyUpdated = true;
      
      // Обновляем глобальные массивы расстояний и предшественников
      for (let v = 0; v < distance.length; v++) {
        if (result.distance[v] < distance[v]) {
          distance[v] = result.distance[v];
          predecessor[v] = result.predecessor[v];
        }
      }
    }
  }
  
  return anyUpdated;
}

function checkNegativeCycleParallel(edges, distance) {
  // Проверка на наличие отрицательных циклов
  for (const [from, to, weight] of edges) {
    if (distance[from] !== Infinity && distance[from] + weight < distance[to]) {
      return { 
        hasNegativeCycle: true,
        cycle: detectCycle(edges, distance)
      };
    }
  }
  
  return { hasNegativeCycle: false };
}

Особенности:

✅ Потенциальное ускорение для очень больших графов при использовании многопоточности

✅ Эффективное использование многоядерных процессоров

❌ Сложная реализация и синхронизация между потоками

❌ Накладные расходы на создание и управление потоками могут перевесить выигрыш на небольших графах

Интуиция за алгоритмом Беллмана-Форда

Ключевая идея алгоритма основана на итеративном улучшении оценок кратчайших путей:

Мы начинаем с расстояния 0 до исходной вершины и бесконечности до всех остальных.
На каждой итерации мы пытаемся улучшить (уменьшить) оценку расстояния до каждой вершины, рассматривая все рёбра графа.
После (|V| - 1) итераций мы гарантированно находим кратчайшие пути, если в графе нет отрицательных циклов.
Дополнительная итерация позволяет проверить наличие отрицательных циклов.

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

Распространённые ошибки

🤦‍♂️ Забывание проверки на наличие отрицательных циклов
😅 Неверное количество итераций (требуется |V| - 1, а не |V|)
🐛 Ошибки при обновлении расстояний и предшественников
😕 Применение алгоритма к графам с отрицательными рёбрами, но без проверки на циклы

Визуализация алгоритма

Рассмотрим пример с графом:

Вершины: 0, 1, 2, 3
Рёбра: (0,1,5), (0,2,2), (1,3,3), (2,1,-2), (2,3,6)

Процесс работы алгоритма:

Инициализация:

distance = [0, Infinity, Infinity, Infinity]
predecessor = [null, null, null, null]

Итерация 1:

Релаксация (0,1,5): distance[1] = 5, predecessor[1] = 0
Релаксация (0,2,2): distance[2] = 2, predecessor[2] = 0
Состояние: distance = [0, 5, 2, Infinity]

Итерация 2:

Релаксация (2,1,-2): distance[1] = 0, predecessor[1] = 2
Релаксация (1,3,3): distance[3] = 3, predecessor[3] = 1
Релаксация (2,3,6): Не изменяется, так как 2 + 6 > 3
Состояние: distance = [0, 0, 2, 3]

Итерация 3:

Все distance остаются неизменными.
Состояние: distance = [0, 0, 2, 3]

Проверка на отрицательные циклы: Все расстояния стабильны, отрицательных циклов нет.

Итоговые кратчайшие пути:

От 0 до 0: [0] с длиной 0
От 0 до 1: [0, 2, 1] с длиной 0
От 0 до 2: [0, 2] с длиной 2
От 0 до 3: [0, 2, 1, 3] с длиной 3

Сравнение с другими алгоритмами поиска кратчайших путей

Алгоритм Беллмана-Форда vs. Алгоритм Дейкстры

Характеристика	Беллман-Форд	Дейкстра
Рёбра с отрицательным весом	✅ Поддерживает	❌ Не поддерживает
Обнаружение отрицательных циклов	✅ Обнаруживает	❌ Не применимо
Временная сложность	O(V×E)	O(E log V) с бинарной кучей
Практическая эффективность	🔄 Средняя	🚀 Высокая для положительных весов
Сфера применения	Более универсальный	Более эффективный при отсутствии отрицательных весов

Алгоритм Беллмана-Форда vs. Алгоритм Флойда-Уоршелла

Характеристика	Беллман-Форд	Флойд-Уоршелл
Тип задачи	Кратчайшие пути из одной вершины	Кратчайшие пути между всеми парами вершин
Временная сложность	O(V×E)	O(V³)
Пространственная сложность	O(V)	O(V²)
Рёбра с отрицательным весом	✅ Поддерживает	✅ Поддерживает
Эффективность на разреженных графах	🚀 Высокая	🔄 Низкая
Эффективность на плотных графах	🔄 Низкая	🚀 Может быть лучше Беллмана-Форда

Оптимизации

SPFA (Shortest Path Faster Algorithm)

Оптимизированная версия алгоритма Беллмана-Форда, использующая очередь:

function spfa(edges, vertices, source) {
  // Преобразуем в список смежности
  const adjList = Array(vertices).fill().map(() => []);
  for (const [from, to, weight] of edges) {
    adjList[from].push({ to, weight });
  }
  
  // Инициализация
  const distance = Array(vertices).fill(Infinity);
  const predecessor = Array(vertices).fill(null);
  const inQueue = Array(vertices).fill(false);
  const queueCount = Array(vertices).fill(0);
  distance[source] = 0;
  
  // Очередь для обработки вершин
  const queue = [source];
  inQueue[source] = true;
  
  while (queue.length > 0) {
    const current = queue.shift();
    inQueue[current] = false;
    
    // Релаксация исходящих рёбер
    for (const { to, weight } of adjList[current]) {
      if (distance[current] + weight < distance[to]) {
        distance[to] = distance[current] + weight;
        predecessor[to] = current;
        
        // Если вершины ещё нет в очереди, добавляем
        if (!inQueue[to]) {
          queue.push(to);
          inQueue[to] = true;
          queueCount[to]++;
          
          // Проверка на отрицательный цикл
          if (queueCount[to] >= vertices) {
            return { hasNegativeCycle: true };
          }
        }
      }
    }
  }
  
  return {
    hasNegativeCycle: false,
    distances: distance,
    predecessors: predecessor
  };
}

Разреженные матрицы для больших графов

function bellmanFordSparseMatrix(edges, vertices, source) {
  // Используем эффективную структуру для разреженных графов
  // например, CSR (Compressed Sparse Row) представление
  
  // Инициализация CSR формата
  const values = [];
  const columnIndices = [];
  const rowPointers = [0];
  let currentPointer = 0;
  
  // Построение CSR представления
  const sortedEdges = [...edges].sort((a, b) => a[0] - b[0]);
  let currentRow = -1;
  
  for (const [from, to, weight] of sortedEdges) {
    // Заполняем промежуточные строки, если нужно
    while (currentRow < from) {
      currentRow++;
      rowPointers.push(currentPointer);
    }
    
    values.push(weight);
    columnIndices.push(to);
    currentPointer++;
  }
  
  // Добавляем оставшиеся указатели строк
  while (currentRow < vertices - 1) {
    currentRow++;
    rowPointers.push(currentPointer);
  }
  
  // Инициализация расстояний
  const distance = Array(vertices).fill(Infinity);
  const predecessor = Array(vertices).fill(null);
  distance[source] = 0;
  
  // Основной алгоритм Беллмана-Форда с CSR
  for (let i = 0; i < vertices - 1; i++) {
    let updated = false;
    
    for (let v = 0; v < vertices; v++) {
      if (distance[v] === Infinity) continue;
      
      // Перебираем все исходящие рёбра из вершины v
      for (let edgeIdx = rowPointers[v]; edgeIdx < rowPointers[v + 1]; edgeIdx++) {
        const to = columnIndices[edgeIdx];
        const weight = values[edgeIdx];
        
        if (distance[v] + weight < distance[to]) {
          distance[to] = distance[v] + weight;
          predecessor[to] = v;
          updated = true;
        }
      }
    }
    
    if (!updated) break;
  }
  
  // Проверка на отрицательные циклы
  // ...
  
  return {
    distances: distance,
    predecessors: predecessor
  };
}

Варианты и приложения алгоритма

Распределённая реализация для очень больших графов

Для распределённых систем с огромными графами:

function distributedBellmanFord(partitions, vertices, source) {
  // Предполагается, что граф разделён на части (partitions),
  // распределённые по разным узлам или процессам
  
  // Инициализация
  const localDistance = Array(vertices).fill(Infinity);
  const localPredecessor = Array(vertices).fill(null);
  
  // Исходная вершина на соответствующем узле
  if (isSourceInLocalPartition(source, partitions)) {
    localDistance[source] = 0;
  }
  
  let globalUpdated = true;
  let iteration = 0;
  
  while (globalUpdated && iteration < vertices - 1) {
    // Локальная релаксация на текущем узле
    let localUpdated = false;
    
    for (const [from, to, weight] of localEdges) {
      if (localDistance[from] !== Infinity && localDistance[from] + weight < localDistance[to]) {
        localDistance[to] = localDistance[from] + weight;
        localPredecessor[to] = from;
        localUpdated = true;
      }
    }
    
    // Синхронизация с другими узлами
    // Обмен граничными вершинами с соседними узлами
    const boundaryUpdates = exchangeBoundaryVertices(localDistance);
    
    // Обновление локальных расстояний на основе полученных данных
    for (const [vertex, newDistance] of boundaryUpdates) {
      if (newDistance < localDistance[vertex]) {
        localDistance[vertex] = newDistance;
        localUpdated = true;
      }
    }
    
    // Глобальная синхронизация для определения, были ли обновления на каких-либо узлах
    globalUpdated = synchronizeUpdates(localUpdated);
    
    iteration++;
  }
  
  // Проверка на отрицательные циклы (распределённая)
  const hasNegativeCycle = checkDistributedNegativeCycle(localDistance, localEdges);
  
  return {
    hasNegativeCycle,
    localDistances: localDistance,
    localPredecessors: localPredecessor
  };
}

Практическое применение: Протоколы маршрутизации

Алгоритмы дистанционно-векторной маршрутизации (например, RIP) используют идеи Беллмана-Форда:

function routingProtocolSimulation(network, initialNode) {
  // Моделирование работы протокола маршрутизации
  const nodes = Object.keys(network);
  const routingTables = {};
  
  // Инициализация таблиц маршрутизации
  for (const node of nodes) {
    routingTables[node] = {};
    for (const dest of nodes) {
      if (node === dest) {
        routingTables[node][dest] = { distance: 0, nextHop: node };
      } else if (network[node][dest]) {
        routingTables[node][dest] = { 
          distance: network[node][dest], 
          nextHop: dest 
        };
      } else {
        routingTables[node][dest] = { 
          distance: Infinity, 
          nextHop: null 
        };
      }
    }
  }
  
  // Моделирование обмена таблицами маршрутизации
  let updated = true;
  let iteration = 0;
  const maxIterations = nodes.length - 1;
  
  while (updated && iteration < maxIterations) {
    updated = false;
    
    for (const node of nodes) {
      // Каждый узел отправляет свою таблицу соседям
      const neighbors = Object.keys(network[node]).filter(n => network[node][n] < Infinity);
      
      for (const neighbor of neighbors) {
        // Сосед обновляет свою таблицу на основе полученной информации
        for (const dest of nodes) {
          const currentDist = routingTables[neighbor][dest].distance;
          const newDist = network[neighbor][node] + routingTables[node][dest].distance;
          
          if (newDist < currentDist) {
            routingTables[neighbor][dest].distance = newDist;
            routingTables[neighbor][dest].nextHop = node;
            updated = true;
          }
        }
      }
    }
    
    iteration++;
  }
  
  // Проверка на сходимость
  if (updated && iteration === maxIterations) {
    return { converged: false, message: "Possible routing loop detected" };
  }
  
  return { 
    converged: true, 
    routingTables: routingTables,
    iterations: iteration
  };
}

Алгоритм Беллмана-Форда для нахождения кратчайшего простого пути

function simplePath(edges, vertices, source, target) {
  // Ограничиваем количество рёбер в пути
  const maxPathEdges = vertices - 1;
  
  // Создаём матрицу dp[v][k] - минимальное расстояние от source до v,
  // используя не более k рёбер
  const dp = Array(vertices).fill().map(() => 
    Array(maxPathEdges + 1).fill(Infinity)
  );
  
  const predecessor = Array(vertices).fill().map(() =>
    Array(maxPathEdges + 1).fill(null)
  );
  
  dp[source][0] = 0;
  
  // Динамическое программирование для построения путей
  for (let k = 1; k <= maxPathEdges; k++) {
    // Сначала копируем значения из предыдущего шага
    for (let v = 0; v < vertices; v++) {
      dp[v][k] = dp[v][k-1];
      predecessor[v][k] = predecessor[v][k-1];
    }
    
    // Затем пытаемся улучшить путь, добавляя ещё одно ребро
    for (const [from, to, weight] of edges) {
      if (dp[from][k-1] !== Infinity && dp[from][k-1] + weight < dp[to][k]) {
        dp[to][k] = dp[from][k-1] + weight;
        predecessor[to][k] = from;
      }
    }
  }
  
  // Восстановление пути
  const path = [];
  let current = target;
  let edgesUsed = maxPathEdges;
  
  // Находим минимальное количество рёбер для оптимального пути
  while (edgesUsed > 0 && dp[target][edgesUsed] === dp[target][edgesUsed-1]) {
    edgesUsed--;
  }
  
  if (dp[target][edgesUsed] === Infinity) {
    return { pathExists: false };
  }
  
  // Восстанавливаем путь
  while (current !== null && current !== source) {
    path.unshift(current);
    current = predecessor[current][edgesUsed];
    edgesUsed--;
  }
  
  if (current === null) {
    return { pathExists: false };
  }
  
  path.unshift(source);
  
  return {
    pathExists: true,
    distance: dp[target][maxPathEdges],
    path: path
  };
}

Заключение

При использовании алгоритма Беллмана-Форда важно помнить:

🌐 Это универсальный алгоритм, который работает с любыми весами рёбер, включая отрицательные
🔄 Обнаружение отрицательных циклов — одно из ключевых преимуществ алгоритма
⚡ Для графов без отрицательных рёбер алгоритм Дейкстры обычно эффективнее
🧠 Различные оптимизации (ранняя остановка, SPFA) могут значительно улучшить производительность
🔍 Алгоритм можно адаптировать для распределённых и параллельных вычислений

Алгоритм Беллмана-Форда является фундаментальным алгоритмом в теории графов и имеет множество практических применений: от сетевой маршрутизации и финансовых систем до анализа цепочек обмена валют и арбитража. Его способность обнаруживать отрицательные циклы делает его особенно ценным в ситуациях, где потенциально существуют возможности для бесконечной оптимизации. 🌟

Попробуй решить популярные задачи

Массивы и Хеширование