Pseudo Code

Урок 4 из 9 курса Алгоритм Беллмана-Форда — Алгоритмы на графах на Coddy.

bellmanFord(n, edges, source):
   dist = [INF, INF, ...]; dist[source] = 0
   repeat (n - 1) times:
      for each edge (u -> v, weight w):
         if dist[u] != INF and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
   replace every remaining INF with -1
   return dist

// отрицательный цикл: если после n-1 проходов какое-либо ребро ВСЕ ЕЩЕ релаксирует,
// значит, существует отрицательный цикл.

Условие dist[u] != INF предотвращает построение путей из недостижимых вершин.
Релаксация всего списка ребер — это один проход. Алгоритм Беллмана-Форда — это просто этот проход, повторенный n - 1 раз.

Попробуйте сами

В этом уроке нет задания по программированию.

Проверьте себя

В этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.

Все уроки раздела Алгоритм Беллмана-Форда — Алгоритмы на графах

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2