Алгоритм Форда-Беллмана (реализация на Java)

Java   26 Март 2012  Автор статьи:  

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

Входные данные:
В первой строке записаны целые числа N и M – количество вершин и количество дуг соответственно (2\le N\le 1000, 0\le M\le 10000). Дальше идет M строк с тройками целых чисел X, Y, W, обозначающими, что дуга из X в Y имеет вес W (1\le X,Y\le N, |W|\le 1000).

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

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

    public static void main(String[] args) {
        Solution solution = new Solution();

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

    private void solve() {
        // Для считывания воспользуемся классом Scanner
        // Для вывода - классом PrintWriter
        Scanner scanner = new Scanner(System.in);
        PrintWriter printWriter = new PrintWriter(System.out);

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

        // Дуги графа будем хранить массиве
        // экземпляров класса Edge
        Edge[] edges = new Edge[edgeCount];

        for (int i = 0; i < edgeCount; i++) {
            // Считываем начальную и конечную вершину
            // i-ой дуги, а также её вес
            int from = scanner.nextInt();
            int to = scanner.nextInt();
            int weight = scanner.nextInt();

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

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

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

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

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

        // В соответствии с алгоритмом будем
        // обновлять массив расстояний
        for (int i = 0; i < vertexCount - 1; i++) {
            for (int j = 0; j < edgeCount; j++) {
                int from = edges[j].from;
                int to = edges[j].to;
                int weight = edges[j].weight;

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

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

        // Выводим расстояние от 0-ой вершины
        // до каждой отличной от нее
        for (int i = 1; i < vertexCount; i++) {
            if (distance[i] == INF) {
                printWriter.println("NO");
            } else {
                printWriter.println(distance[i]);
            }
        }

        // После выполнения программы необходимо закрыть
        // потоки ввода и вывода
        scanner.close();
        printWriter.close();
    }

    // Для удобства хранения дуг графа создадим
    // класс, содержащий информацию о весе дуги,
    // начальной и конечной вершинах дуги
    public class Edge {
        int from;
        int to;
        int weight;

        public Edge(int u, int v, int w) {
            this.from = u;
            this.to = v;
            this.weight = w;
        }
    }
}

  • Сания

    Он должен выводить именно вершины в конце??? так как на моих примерах он выводит совсем другие значения.

    • http://cybern.ru/ lordrp

      Читай выходные данные в начале статьи. Код сто процентов рабочий.

  • Сания

    Он должен выводить именно вершины в конце??? так как на моих примерах он выводит совсем другие значения.

    • http://cybern.ru/ lordrp

      Читай выходные данные в начале статьи. Код сто процентов рабочий.

Научиться программировать

  • на Delphi

  • на Java

  • на C++