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

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.

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

Tema

Pbinfo

• dmin
• Roy-Floyd
• rf

Infoarena

• royfloyd
• rfinv
• coach