Алгоритм Беллмана-Форда

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

Алгоритм решения.

Предположим сначала, что граф не содержит циклов отрицательного веса.

Пусть N – количество вершин графа, M – количество дуг, – вес дуги, ведущей из вершины i в вершину j. Обозначим за вес кратчайшего пути из v в j, который содержит не более i дуг. В случае отсутствия такого пути положим , где бесконечность – это некоторое значение, заведомо превосходящее все возможные расстояния. При существует единственный допустимый путь – путь из вершины v в неё саму, имеющий нулевой вес. Соответственно, при . Пусть теперь . Понятно, что кратчайший путь из вершины v в вершину j состоит из кратчайшего пути из v в некоторую вершину p и дуги . Тогда можно записать следующие рекуррентные соотношения:

Здесь V — множество вершин графа, E — множество дуг.

Отметим, что оптимальный путь не должен содержать циклов. В самом деле, если у нас есть некоторый путь с циклом, то, выбросив цикл, мы получим путь меньшего либо равного веса. Тогда максимальное количество дуг в пути будет равно N-1 (в противном случае в пути появится цикл).

Если реализовывать алгоритм непосредственно по приведённым выше соотношениям, то его сложность составит O( M). Попробуем улучшить эту оценку. Заметим, что для каждой дуги можно однозначно определить, при решении подзадач для какой именно вершины она будет использована. Тогда, вместо того чтобы при каждом i перебирать все вершины и для каждой из них все рёбра, можно просто перебрать все рёбра. Получаем асимптотическую сложность O(NM).

Кроме того, нет смысла хранить всю матрицу весов кратчайших путей. Достаточно лишь двух её последних строк. Если же мы немного отойдём от составленных рекуррентных соотношений, то сможем обойтись всего одной строкой. В самом деле, будем брать веса вспомогательных путей из некоторой строки и записывать улучшенные значения в неё же. Тогда после завершения i -ой итерации могут быть найдены веса оптимальных путей, содержащих более чем i дуг, однако все кратчайшие пути, содержащие t дуг, гарантированно будут найдены после выполнения t -ой итерации (действительно, они либо будут найдены на t -ой итерации в соответствии с рекуррентными соотношениями, либо ранее).

Предположим, что нам необходимо вывести также сам кратчайший путь. Тогда для каждой подзадачи необходимо будет сохранять предпоследнюю вершину в пути, т.е. значение k. Это значит, что понадобится матрица размерности NM.

Итак, если все циклы в графе имеют неотрицательный вес, то для нахождения весов кратчайших путей будет достаточно N-1 итерации. Но в противном случае ситуация изменится. Если в пути есть цикл отрицательного веса, то мы можем двигаться по нему бесконечно долго, каждый раз уменьшая длину пути. Произведём тестовую N -ую итерацию. Если после неё изменились какие-то из ранее вычисленных расстояний, то это равносильно тому, что в графе есть цикл отрицательного веса.

Задача 1

Дан взвешенный ориентированный граф из N вершин и M дуг. В графе могут быть как петли, так и дуги отрицательного веса. Требуется найти расстояние от первой вершины до всех остальных. Известно, что в графе нет циклов отрицательного веса и между любой парой вершин не может быть более одной дуги в одном направлении.

Входные данные:

В первой строке записаны целые числа N и M – количество вершин и количество дуг соответственно . Дальше идет M строк с тройками целых чисел X, Y, W, обозначающими, что дуга из X в Y имеет вес W .

Выходные данные:

Вывести N-1 строку – длины кратчайших путей от первой вершины до всех остальных вершин в порядке возрастания их номеров. Если же до некоторой вершины не существует пути из первой, то в соответствующей строке необходимо вывести «NO».

1. import java.io.PrintWriter;

2. import java.util.Arrays;

3. import java.util.Scanner;

4. public class Solution {

5. private static final int INF = 1000 * 1000 * 1000; //в качестве условной бесконечности выберем достаточно большое число 10^9

6. public static void main(String[] args) {

7. Solution solution = new Solution();

8. solution.solve(); //вызываем процедуру решения задачи

9. }

10. private void solve() {

11. Scanner scanner = new Scanner(System.in);//для считывания воспользуемся классом Scanner

12. PrintWriter printWriter = new PrintWriter(System.out); //для считывания воспользуемся классом PrintWriter

13. int vertexCount = scanner.nextInt(); //считываем число вершин графа

14. int edgeCount = scanner.nextInt(); //считываем число дуг графа

15. Edge[] edges = new Edge[edgeCount]; //дуги графа будем хранить в массиве

16. for (int i = 0; i < edgeCount; i++) { //экземпляров класса Edge

17. int from = scanner.nextInt(); //считываем начальную вершину i-ой дуги

18. int to = scanner.nextInt(); //считываем конечную вершину i-ой дуги

19. int weight = scanner.nextInt(); //считываем вес i-ой дуги

20. from--;

21. to--; //так как нами используется 0-ая индексация, то уменьшим индексы вершин на единицу

22. edges[i] = new Edge(from, to, weight); //кладём считанную дугу в массив дуг

23. }

24. int [] distance = new int [vertexCount]; //создаем массив, i-ый элемент которого будет хранить текущее расстояние от 1-ой (или 0-ой в нашем случае 0-индексации) до i-ой вершины графа

25. Arrays.fill(distance, INF); //до начала работы алгоритма все расстояния, кроме 0-го, равны бесконечности (условной)

26. distance[0] = 0; //0-ое расстояние, очевидно равно нулю,
так как расстояние от 0-ой вершины до самой себя равно нулю

27. for (int i = 0; i < vertexCount - 1; i++) {

28. for (int j = 0; j < edgeCount; j++) {

29. int from = edges[j].from;

30. int to = edges[j].to;

31. int weight = edges[j].weight; //в соответствии с алгоритмом будем обновлять массив расстояний

32. if (distance[from] == INF) { //ясно, что если вершина from на текущем шаге работы алгоритма находится бесконечно далеко от 0-ой, то она не изменит ответ

33. continue;

34. }

35. distance[to] = Math.min(distance[to], //В противном случае обновим расстояние до вершины to, это называют релаксацией

36. distance[from] + weight);

37. }

38. }

39. for (int i = 1; i < vertexCount; i++) {

40. if (distance[i] == INF) {

41. printWriter.println("NO");

42. }

43. else {

44. printWriter.println(distance[i]); //выводим расстояние от 0-ой вершины до каждой отличной от нее