Флойд | java@Cat

Задача

Постановка задачи на e-olymp.

Дан ориентированный взвешенный граф. Найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.

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

В первой строке содержится количество вершин графа [latex]n[/latex] [latex](1 \leq n \leq 100)[/latex]. В следующих [latex]n[/latex] строках находится по [latex]n[/latex] чисел, которые задают матрицу смежности графа. В ней -1 означает отсутствие ребра между вершинами, а любое неотрицательное число — присутствие ребра данного веса. На главной диагонали матрицы всегда расположены нули.

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

Вывести искомое максимальное кратчайшее расстояние.

Тесты

№	n	matrix	Результат
1	4	0 5 9 -1 -1 0 2 8 -1 -1 0 7 4 -1 -1 0	16
2	3	0 -1 2 2 0 -1 4 1 0	4
3	5	0 -1 -1 3 4 2 0 3 -1 4 -1 4 0 -1 4 3 -1 2 0 1 1 1 -1 -1 0	8

Ссылка на успешно пройденные тесты на сайте e-olymp.

Решение

import java.util.*;
public class Graph {

    public static void main(String[] args){
        Scanner input =  new Scanner(System.in);

        int n, max = 0;
        n = input.nextInt();
        int[][] matrix = new int[n][n];

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                matrix[i][j] = input.nextInt();
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                for(int k = 0; k < n; k++){
                    if(j != k && matrix[j][i] != -1 && matrix[i][k] != -1){
                        if(matrix[j][k] == -1)
                            matrix[j][k] = matrix[j][i] + matrix[i][k];
                        else
                            matrix[j][k] = Math.min(matrix[j][k], matrix[j][i] + matrix[i][k]);
                    }
                }
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] > max) max = matrix[i][j];
            }
        }

        System.out.println(max);
    }
}

import java.util.*;

public class Graph {

public static void main(String[] args){

Scanner input = new Scanner(System.in);

int n, max = 0;

n = input.nextInt();

int[][] matrix = new int[n][n];

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

matrix[i][j] = input.nextInt();

}

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

for(int k = 0; k < n; k++){

if(j != k && matrix[j][i] != -1 && matrix[i][k] != -1){

if(matrix[j][k] == -1)

matrix[j][k] = matrix[j][i] + matrix[i][k];

else

matrix[j][k] = Math.min(matrix[j][k], matrix[j][i] + matrix[i][k]);

}

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

if(matrix[i][j] > max) max = matrix[i][j];

}

System.out.println(max);

}

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Данная задача решается при использовании алгоритма Флойда-Уоршелла, суть которого состоит в нахождении длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Код данного алгоритма можно наблюдать в цикле по [latex]i[/latex], в котором имеются два вложенных цикла по [latex]j[/latex] и по [latex]k[/latex]. Здесь мы проходим по элементам матрицы смежности графа, проверяя существует ли ребро между вершинами. Далее следуя алгоритму Флойда выполняем следующее действие — с помощью функции Math.min() находим минимальный путь из одной вершины в другую, записывая его в матрицу. По нахождении всех кратчайших путей, находим максимальный из них, и выводим его в консоль.

Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

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

В первой строке записано количество вершин графа n (1 ≤ [latex]n[/latex] ≤ 100). В следующих n строках записано по [latex]n[/latex] чисел — матрица смежности графа ([latex]j[/latex]-ое число в [latex]i[/latex]-ой строке соответствует весу ребра из вершины [latex]i[/latex] в вершину [latex]j[/latex]). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

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

Выведите [latex]n[/latex] строк по [latex]n[/latex] чисел — матрицу кратчайших расстояний между парами вершин. [latex]j[/latex]-ое число в [latex]i[/latex]-ой строке должно равняться весу кратчайшего пути из вершины [latex]i[/latex] в вершину [latex]j[/latex].

Алгоритм

(взято с Википедии)

Пусть вершины графа [latex]{\displaystyle G=(V,\;E),\;|V|=n}[/latex] пронумерованы от 1 до [latex] {\displaystyle n}[/latex] и введено обозначение [latex]{\displaystyle d_{ij}^{k}}[/latex] для длины кратчайшего пути от [latex] {\displaystyle i}[/latex] до [latex]{\displaystyle j}[/latex], который кроме самих вершин [latex] {\displaystyle i,\;j} [/latex] проходит только через вершины [latex]{\displaystyle 1\ldots k} [/latex]. Очевидно, что [latex]{\displaystyle d_{ij}^{0}} [/latex] — длина (вес) ребра [latex]{\displaystyle (i,\;j)}[/latex], если таковое существует (в противном случае его длина может быть обозначена как [latex]{\displaystyle \infty } [/latex] ).

Существует два варианта значения [latex] {\displaystyle d_{ij}^{k},\;k\in \mathbb {(} 1,\;\ldots ,\;n)} d_{ij}^{k},\;k\in \mathbb {(} 1,\;\ldots ,\;n)[/latex]:

Кратчайший путь между [latex]{\displaystyle i,\;j}[/latex] не проходит через вершину [latex] {\displaystyle k}[/latex], тогда [latex]{\displaystyle d_{ij}^{k}=d_{ij}^{k-1}}[/latex] Существует более короткий путь между [latex]{\displaystyle i,\;j}[/latex], проходящий через [latex]{\displaystyle k}[/latex], тогда он сначала идёт от [latex]{\displaystyle i} [/latex] до [latex] {\displaystyle k} [/latex], а потом от [latex] {\displaystyle k} [/latex] до [latex] {\displaystyle j} [/latex]. В этом случае, очевидно, [latex]{\displaystyle d_{ij}^{k}=d_{ik}^{k-1}+d_{kj}^{k-1}}[/latex]

Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.

Тогда рекуррентная формула для [latex]{\displaystyle d_{ij}^{k}}[/latex] имеет вид:

[latex]{\displaystyle d_{ij}^{0}}[/latex] — длина ребра [latex] {\displaystyle (i,\;j);} (i,\;j);[/latex] [latex]{\displaystyle d_{ij}^{k}=\min(d_{ij}^{k-1},\;d_{ik}^{k-1}+d_{kj}^{k-1}).}[/latex]

Алгоритм Флойда-Уоршелла последовательно вычисляет все значения [latex]{\displaystyle d_{ij}^{k},} [/latex], [latex]{\displaystyle \forall i,\;j}[/latex] для [latex] {\displaystyle k} [/latex] от 1 до [latex] {\displaystyle n} [/latex]. Полученные значения [latex] {\displaystyle d_{ij}^{n}}[/latex] являются длинами кратчайших путей между вершинами [latex]. {\displaystyle i,\;j.} [/latex].

Код

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;


class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
			Scanner in =new Scanner(System.in);
			int n = in.nextInt();
			int w[][] = new int[n][n];	 
			for( int i = 0 ; i < n ; i++ ){
				for( int j = 0 ; j < n ; j++ ){
					w[i][j] = in.nextInt();
				}
			}
	
			for( int k = 0 ; k < n ; k++ ){
				for( int i = 0 ; i<n ; i++ ){
					for( int j=0 ; j<n ; j++ ){
					    w[i][j] = Math.min(w[i][j], w[i][k] + w[k][j]);
					}
				}
			}
    
			for( int i = 0 ; i < n ; i++ ){
				for( int j = 0 ; j < n ; j++ ){
		    		System.out.print(w[i][j] + " ");
				}
				System.out.println();
    		}
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in =new Scanner(System.in);

int n = in.nextInt();

int w[][] = new int[n][n];

for( int i = 0 ; i < n ; i++ ){

for( int j = 0 ; j < n ; j++ ){

w[i][j] = in.nextInt();

}

for( int k = 0 ; k < n ; k++ ){

for( int i = 0 ; i<n ; i++ ){

for( int j=0 ; j<n ; j++ ){

w[i][j] = Math.min(w[i][j], w[i][k] + w[k][j]);

}

for( int i = 0 ; i < n ; i++ ){

for( int j = 0 ; j < n ; j++ ){

System.out.print(w[i][j] + " ");

}

System.out.println();

}

Условие на e-olymp.com
Решение на e-olymp.com
Код на ideone.com

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: Флойд

e-olymp 975. Флойд

Задача

Тесты

Решение

Пояснения

e-olymp 974. Флойд-1

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

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

Алгоритм

Код