Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Algoritmul Roy-Floyd

Adăugată de :
sorynsoo
Sursă :
IronCoders
Autor :
sorynsoo
Grupă :
Mare
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
100 ms
Limită memorie :
1024 kbytes

Roy-Floyd

 

Algoritmul Roy-Floyd are ca scop gasirea unui drum de cost minim intre oricare pereche de noduri din graf .Pentru a se determina drumurile minime se foloseste o matrice iar din cauza complexitatii de  O(n^3)  este considerat a fi ineficient .

 

Cerinta

Se dă un graf orientat cu N noduri   Sa se găsească pentru oricare pereche de noduri X , Y  lungimea minima a drumului dintre acestea.

 

Date de intrare

Pe prima linie se afla N .

Pe următoarele N linii se afla N numere cu semnificatia ca numarul de pe linia i si coloana j reprezinta costul muchiei de la nodul i la nodul j .

 

Date de iesire

Se va scrie matricea drumurilor de cost minim ( N linii si N coloane )  rezultata din executia algoritmului.

 

Rezolvare: Click

 

Restrictii

 N < = 100

 Daca nu exista muchie intre nodul i si j atunci in matrice pe linia i si coloana j se va afla valoarea 0.

 

Exemplu

 

 Date intrare  Date iesire
 4
 0 4 2 1
 2 0 0 2
 0 1 0 6
 3 0 4 0
 0 3 2 1 
 2 0 4 2 
 3 1 0 3 
 3 5 4 0 

 


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Grafuri


Comentarii

Adauga un comentariu: Click !