Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <sstream>
- #include <fstream>
- #define inf 9999
- using namespace std;
- //---zmienne_globalne----
- struct Edge
- {
- int weight;
- int beg;
- int end;
- }*E;
- int n,m;
- int *bell;
- //-----------------------
- void wczytaj(void);
- bool Bellman(Edge *e,int wielkosc , int licznik);
- void zmiana_wag(Edge *e, int *h,int m);
- int *Dijkstry(int s, int n);
- void finalizacja(int *h , int **q2);
- int main()
- {
- wczytaj();
- for(int i=0; i<m; i++)
- {
- cout<<E[i].beg<<" "<<E[i].end<<" "<<E[i].weight <<endl;
- }
- cout<<endl;
- cout<<m<<endl;
- bool wykonaj;
- int *q=new int[n+1];
- int **q2=new int*[n];
- wykonaj=Bellman(E,n+1, m);
- if(wykonaj==true){
- int *h=bell;
- zmiana_wag(E,h, m);
- for(int i=0;i<=n;i++){
- q2[i]=Dijkstry(i, n);
- }
- for(int i=0;i<=n;i++){
- for(int j=0;j<=n;j++){
- cout<<q2[i][j]<<" ";
- }
- cout<<endl;
- }
- finalizacja(h,q2);
- //----zwolnienie pamieci----
- for(int i=0;i<n+1;i++){
- delete [] q2[i];
- }
- delete [] h;
- }
- else{
- cout<<"Algorytm Johnsona nie zadzia³a";
- }
- delete [] q;
- delete [] *q2;
- }
- bool Bellman(Edge *e, int wielkosc, int m)
- {
- bell=new int [wielkosc];
- for(int i=0; i<wielkosc; i++)bell[i]=0;
- bool sprawdz=false;
- while(!sprawdz)
- {
- sprawdz=true;
- for(int i=0; i<m; i++)
- {
- if(bell[e[i].end]>bell[e[i].beg]+e[i].weight)
- {
- bell[e[i].end]=bell[e[i].beg]+e[i].weight;
- sprawdz=false;
- }
- }
- }
- for(int i=0;i<m;i++){
- if(bell[e[i].end]>(bell[e[i].beg]+e[i].weight))return false;
- }
- return true;
- }
- int *Dijkstry(int s, int n)
- {
- //-------tworzenie macierzy wag-----------
- int **A=new int*[n+1];
- for(int i=0;i<=n;i++)A[i]=new int[n+1];
- for(int i=0;i<=n;i++){
- for(int j=0;j<=n;j++){
- if(i==j){
- A[i][j]=0;
- }
- else{
- A[i][j]=inf;
- }
- }
- }
- for(int i=0;i<m;i++){
- A[E[i].beg][E[i].end]=E[i].weight;
- }
- /* for(int i=1;i<=n;i++){
- for(int j=1;j<=n;j++){
- cout<<A[i][j]<<" ";
- }
- cout<<endl;
- }*/
- //----------------------------------------------
- int *dist=new int[n+1];
- int *pred=new int[n+1];
- int* fin = new int[n+1];
- for (int v = 0; v <= n; v++) {
- dist[v] = inf;
- fin[v] = 0;
- pred[v] = -1;
- }
- dist[s] = 0;
- fin[s] = 1;
- int last = s, y = 0, temp = inf;
- for (int i = 1; i < n; i++) {
- for (int v = 0; v <= n; v++) {
- if ((A[last][v] < inf) && (fin[v] == 0)) {
- if (dist[last] + A[last][v] < dist[v]) {
- dist[v] = dist[last] + A[last][v];
- pred[v] = last+1;
- }
- }
- temp = inf;
- y = 0;
- for (int u = 0; u < n; u++) {
- if ((fin[u] == 0) && (dist[u] < temp)) {
- y = u;
- temp = dist[u];
- }
- }
- }
- if (temp < inf) {
- fin[y] = 1;
- last = y;
- }
- }
- delete[] fin;
- // cout<<endl<<"!";
- // for(int i=1;i<=n;i++)cout<<dist[i]<<" ";
- return dist;
- }
- void zmiana_wag(Edge *e, int *h, int m)
- {
- for(int i=0; i<m; i++)
- {
- e[i].weight=e[i].weight+h[e[i].beg]-h[e[i].end];
- }
- }
- void finalizacja(int *h, int **q2)
- {
- int **D=new int*[n];
- for(int i=0;i<n;i++){
- D[i]=new int[n];
- }
- cout<<endl;
- for(int i=0;i<=n;i++)cout<<h[i]<<" ";
- cout<<endl;
- cout<<endl;
- for(int i=0;i<n;i++){
- for(int j=0;j<n;j++){
- if(q2[i+1][j+1]==inf || h[j+1]==inf || h[i+1]==inf){
- D[i][j]=inf;
- }
- else{
- D[i][j]=q2[i+1][j+1]+h[j+1]-h[i+1];
- }
- }
- }
- //----zapis------
- ofstream out;
- out.open("Out0502.txt");
- for(int i=0;i<n;i++){
- for(int j=0;j<n;j++){
- out<<D[i][j]<<" ";
- }
- out<<'\n';
- }
- out.close();
- //------zwolnienie pamieci----
- for(int i=0;i<n;i++){
- delete [] D[i];
- }
- delete [] *D;
- }
- void wczytaj(void)
- {
- int i=0, licznik=0,sumka=0,s=0;
- ifstream wej;
- wej.open("In0502.txt");
- int pom2[100]= {0};
- string pom;
- while(!wej.eof())
- {
- getline(wej,pom);
- sumka=0;
- for(int k=0; k<pom.size(); k++)
- {
- if(pom[k]==' ')
- {
- sumka++;
- licznik++;
- }
- }
- pom2[i]=sumka+1;
- if(pom.size()>0)
- licznik++;
- sumka=0;
- i++;
- }
- wej.close();
- wej.open("In0502.txt");
- wej>>n;
- int x=1;
- licznik=licznik/2;
- E = new Edge[licznik];
- m=licznik;
- i=0;
- while(!wej.eof())
- {
- for(int j=1; j<pom2[x]; j=j+2)
- {
- wej>>E[i].end;
- wej>>E[i].weight;
- E[i].beg=x;
- i++;
- }
- x++;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement