Bella: /* Algoritmul Roy Floyd */

2020-03-23T10:53:29Z

Algoritmul Roy Floyd

New page

==Algoritmul Roy Floyd ==
[https://infoarena.ro/problema/royfloyd Royfloyd]

Se da un graf orientat cu '''N''' noduri, memorat prin matricea ponderilor. Sa se determine pentru orice pereche de noduri x si y lungimea minima a drumului de la nodul x la nodul y si sa se afiseze matricea drumurilor minime. Prin lungimea unui drum intelegem suma costurilor arcelor care-l alcatuiesc.

<syntaxhighlight>
/// doar distanta minima de la toate nodurile la toate
/// se afiseaza matricea drumurilor minime rezultate
/// complexitate n^3
#include <stdio.h>

int n, a[105][105];

void citire(){
freopen("royfloyd.in","r",stdin);
freopen("royfloyd.out","w",stdout);

int i, j;
scanf( "%d", &n);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
scanf("%d",&a[i][j]);
}

void roy_floyd(){
int i, j, k;
for ( k = 1; k <= n; k++ )
for ( i = 1; i <= n; i++ )
for ( j = 1; j <= n; j++ )
if ( i != j && a[i][k] && a[k][j] && ( a[i][j] > a[i][k] + a[k][j] || !a[i][j] ) )
a[i][j] = a[i][k] + a[k][j];
}

void afis(){
int i, j;
for ( i = 1; i <= n; i++ ) {
for ( j = 1; j <= n; j++ )
printf( "%d ",a[i][j] );
printf( "\n" );
}
}
int main(){
citire();
roy_floyd();
afis();
return 0;
}

</syntaxhighlight>

[https://infoarena.ro/problema/r Roy Floyd]
Aceeasi problema. Vom afisa suplimentar, pe langa matricea cu drumurile minime de la oricare doua noduri si o a doua matrice ce va retine cate strazi maxim pargurg pe drumurile minime.
<syntaxhighlight>
#include <bits/stdc++.h>
using namespace std;

ifstream f("rf.in");
ofstream g("rf.out");

const int N = 1001;
int a[N][N], b[N][N];
int n;

void citire() {
f >> n;
for( int i = 1; i <= n; i++ )
for( int j = 1; j <= n; j++ ) {
f >> a[i][j];
if( i != j )
b[i][j] = 1;
}
}

void roy() {
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if((a[i][j] > a[i][k] + a[k][j]) or (a[i][j] == a[i][k] + a[k][j] and b[i][j] < b[i][k] + b[k][j])) {
b[i][j] = b[i][k] + b[k][j];
a[i][j] = a[i][k] + a[k][j];
}
}

void afisare() {
for( int i = 1; i <= n; i++ ) {
for(int j = 1; j <= n; j++ )
g << a[i][j] << " ";
g << "\n";
}
for( int i = 1; i <= n; i++ ) {
for( int j = 1; j <= n; j++ )
g << b[i][j] << " ";
g << "\n";
}
}

int main() {
citire();
roy();
afisare();
}
</syntaxhighlight>

= Tema =
Pbinfo
*[https://www.pbinfo.ro/probleme/1604/dmin dmin]
*[https://www.pbinfo.ro/probleme/589/roy-floyd Roy-Floyd]
*[https://www.pbinfo.ro/probleme/1652/rf rf]

Infoarena
*[https://infoarena.ro/problema/royfloyd royfloyd]
*[https://infoarena.ro/problema/rfinv rfinv]
*[https://infoarena.ro/problema/coach coach]

Clasa a XI-a lecția 26 - Revision history

Bella: /* Algoritmul Roy Floyd */