# Difference between revisions of "Clasa a XI-a lecția 26"

## Algoritmul Roy Floyd

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.

```/// doar distanta minima de la un 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 (a[i][k] && a[k][j] && (a[i][j] > a[i][k] + a[k][j] || !a[i][j]) && 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;
}

```

Roy Floyd Aceeasi problema. Vom afisa suplimentar, pe langa matricea cu drumurile minime de la oricare doua nori si o a doua matrice ce va retine cate strazi maxim pargurg pe drumurile minime.

```#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();
}
```

Pbinfo

Infoarena