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

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

Дан взвешенный ориентированный граф из N вершин. Требуется найти в нем величину кратчайшего пути между каждой парой вершин.

Входные данные:
В первой строке записано натуральное число N (1\le N\le 100). В каждой из следующих N строк записано по N чисел — матрица весов дуг графа. Все веса представляют собой целые неотрицательные числа, не превосходящие 1000. Если в мартице в i-й строке j-м столбце стоит 0, то это означает, что дуги из вершины i в вершину j нет.

Выходные данные:
В выходной файл надо вывести матрицу кратчайших путей между каждой парой вершин графа (т.е. матрицу у которой в i-й строке j-м столбце столбце стоит длина кратчайшего пути из вершины i в вершину j или 0 — если пути из i в j не существует).

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
import java.io.PrintWriter;
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[][] g = new int[vertexCount][vertexCount];

        for (int i = 0; i < vertexCount; i++) {
            for (int j = 0; j < vertexCount; j++) {
                // Считываем вес ребра между вершинами
                // i и j соответственно
                g[i][j] = scanner.nextInt();

                // По условию если g[i][j] = 0, то это
                // означает, что дуги из i в j нет;
                // в этом случае расстояние между этими
                // вершинами бесконечно велико
                if (g[i][j] == 0) {
                    g[i][j] = INF;
                }
            }
        }

        // Согласно алгоритму будем обновлять
        // ответ для каждой пары вершин i и j,
        // перебирая промежуточную вершину k
        for (int k = 0; k < vertexCount; k++) {
            for (int i = 0; i < vertexCount; i++) {
                for (int j = 0; j < vertexCount; j++) {                
                    g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
                }
            }
        }

        // Для каждой пары вершин выведем величину
        // кратчайшего пути от i до j, или 0,
        // если j не достижима из i
        for (int i = 0; i < vertexCount; i++) {
            for (int j = 0; j < vertexCount; j++) {
                if (g[i][j] == INF) {
                    printWriter.print(0 + " ");
                } else {
                    printWriter.print(g[i][j] + " ");
                }
            }

            printWriter.println();
        }

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

  • Alex

    при вводе

    4
    0 1 1 0
    1 0 0 1
    1 0 0 0
    0 1 0 0
    получаем:
    2 1 1 2
    1 2 2 1
    1 2 2 3
    2 1 3 2

    почему не так?

    0 1 1 2
    1 0 2 1
    1 2 0 3
    2 1 3 0

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

  • на Delphi

  • на Java

  • на C++