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

From Algopedia
Jump to navigationJump to search
(Created page with "==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...")
(No difference)

Revision as of 10:08, 23 March 2020

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

Tema

Pbinfo

Infoarena