Алгоритм Форда-Беллмана (реализация на 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».


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; } } }

  • Сания

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

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

  • Сания

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

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

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

  • на Delphi

  • на Java

  • на C++